数据结构期末试题及答案.doc

E 卷一、单项选择题
1、线性表若采用链式结构时，要求内存中可用存储单元的地址( )。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续不连续都可以
2、判定一个栈ST(最多元素为m0)为空的条件是( )。
A. ST->top!=0 B. ST->top==0
C. ST->top!=m0 D. ST->top==m0
3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列j下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( )。
A. SA+141 B. SA+144
C. SA+222 D. SA+225
4、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：
addr(15)=4
addr(38)=5
addr(61)=6
addr(84)=7
其余地址为空
如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。
A. 8 B. 3 C. 5 D. 9
5、在线索化二叉树中，t所指结点没有左子树的充要条件是( )。
A. t->left==NULL B. t->ltag==1
C. t->ltag==1且t->left==NULL D. 以上都不对
6、将递归算法转换成对应的非递归算法时，通常需要使用( )。
A. 栈 B. 队列 C. 链表 D. 树
7、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，( )次比较后查找成功。
A. 1 B. 2
C. 4 D. 8
8、对一个满二叉树，m个树叶，n个结点，深度为h，则( )。
A. n=h+m B. h+m=2n
C. m=h-1 D. n=2h-1
9、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_____查找方法。
A. 分块 B. 顺序
C. 二分 D. 散列
10、快速排序方法在( )情况下最不利于发挥其长处。
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为奇数
11、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为________.
A.e B.2e C.-e D. -2e
12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点相关的所有弧的时间复杂度是_________.
A.O(n) B.O(e) C.O(n+e) D.O(n*e)
13. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是_________.
A. 选择排序 B. 希尔排序
C. 归并排序 D. 快速排序
14. 适宜于对动态查找表进行高效率查找的组织结构是_____.
A.有序表 B. 分块有序表
C. 三叉排序表 D.线性链表
15. 不定长文件是指__________.
A. 文件的长度不固定 B.记录的长度不固定
C. 字段的长度不固定 D.关键字项的长度不固定
二、填空题
16、对数据间关系的描述是数据的逻辑结构，形式地可以用一个二元组 B=（D，R）来表示，其中D表示________；R表示___________。
17、数据结构的存储一有两种，分为_______和________.
18、评价一个数据结构，基本来说有两条，一条是_______，二是_______。
19、栈的类型说明为：
typedef struc stack{
datatype s(maxlen);
int len;
} stack;
则：POP（stack st）;算法是：
if st.len=0 printf(“underflow” )
else__________;
20、二叉树的第i层上至多有______结点，深度为k的二叉树至多有________结点。
21、图的遍历主要有________和_________两种.
22、在hq的链队中，判定只有一个结点的条件是____________。
23、在散列函数H(key)=key%p中，p应取_________。
24、对于长度为n的线性表，若采用二分法查找，则时间复杂度为_____；若采用分块查找(假定总块数和每块长度均接近n的平方根)，则时间复杂度为_________。
三、解答操作题（每小题 5 分，共 20 分）
25、已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示：

（1）画出该图的图形。（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，并写出遍历序列。
26、把下列二叉树换成二森林，画出图形

27、已知一个散列表如下表示：

35

20

33

48

59
0 1 2 3 4 5 6 7 8 9 10 11 12
其散列函数h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：
=(h(key))+i*h(key)%m i=0,1,…,m-1
其中
h(key)=key%11+1
回答以下问题：
（1）对表中关键字35，20，33 和 48进行查找时，所需要进行的比较次数各为多少？
（2）该散列表在等概率查找时查找成功的平均查找长度为多少？
28、已知序列{17,18,60,40,7,32,73,65,85},请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。
四、算法阅读题(每小题 6 分，共 12 分)
29、面给出了起泡排序算法，请填写算法中的空框，使算法正确。
struct node {　　　　　　　　int　　key;
　　　　　　　　datatype info;
　　　　　　　} node,*lnode；
　　int i，j;
int flag;
　　node　X;
node 　R[n];
① [每循环一次作一次起泡]
循环 i以1为步长，从1到n－1，执行下列语句
(1)(　　　　)
(2)循环 j以1为步长，(　　　　)，执行
若(　　　　)＜R[j].key
则flag ← 1；
X←R[j]；(　　　　)；R[j＋1] ← X
(3)若(　　　　)
则跳出循环
② 算法结束
30、下面给出了在对称序穿线树中找指定结点在后序下的前驱算法，请填写算法中的空框，使算法正确。
struct node {　　　　　　　　datatype 　info;
　　　　　　　　node *llink，*rlink;
　　　　　　　 } *lnode；
　　 lnode p;　　　[p指向指定结点]
　　　　lnode q;　　　[q指向指定结点在后序下的前驱]
①　若p->rlink＞0
则(　　　　)，算法结束
否则q ← p
②　(1)　循环 当(　　　　)时，反复执行
　 (　　　　)
(2)　(　　　　)
③　算法结束
五、算法设计题（共8分）31.设有一个循环双链表，其中有一结点的指针为p,编写一个函数p与其右边的一个结点进行交换。结点结构为

E 卷
一、单项选择题
1. D 2. B 3. C 4. D 5. B 6. A 7. C 8. D 9. A 10. C 11.D 12. C 13. D 14. C 15. B
二、填空题
16． 数据集合 数据间的关系
17． 顺序 非顺序
18． 时间复杂度 空间复杂度
19． st.len=st.len-1
20． 2i-1 2k-1
21． 深度 广度
22． hq->front=hq->rear
23． 素数
24． O(log2n) O( n )
三、解答操作题（每小题 5 分，共 20 分）
25、

深度优先遍历序列为：abdce; 广度优先遍历序列为：abedc
26、

27、答：（1）比较次数分别为3、2、1、1。
（2）平均查找长度 ASL=(3+2+1+1+2)/5=1.8
28、 初始：17，18，60，40，7，32，73，65，85
第1趟：17，18，40，7，32，60，65，73，85
第2趟：17，18，7，32，40，60，65，73，85
第3趟：17，7，18，32，40，60，65，73，85
第4趟：7，17，18，32，40，60，65，73，85
第5趟：7，17，18，32，40，60，65，73，85

四、算法阅读题（每小题 6 分，共 12 分）
29．(1)　flag = 0；
　 (2)　1到n-1；
　 (3)　R[j＋1].key；
　 (4)　R[j] =R[j＋1]；
　　(5)　flag＝0
　30．　q = p->.rlink
　　　　q->link ＜ 0
　　　　q =(－1)*(q->llink)
　　　　q = q->.llink
五、算法设计题（共8分）
参考答案
void swap(dnode*p)
{
dnode * q;
q=p->right;
if (q==NULL )
printf(“不能进行交换!/n”);
else
{
p->right=q->right;
p->right->left=p;
p->left->right=q;
q->left=p->left;
p->left=q;
q->right=p;
}
}