北京理工大学-数据结构期末考试试题（八）

数据结构试卷（八）

一、选择题(30分)

1. 字符串的长度是指（ ）。

(A)串中不同字符的个数 (B) 串中不同字母的个数

(C)串中所含字符的个数 (D) 串中不同数字的个数

2. 建立一个长度为n的有序单链表的时间复杂度为（ ）

(A)O(n) (B) O(1) (C) O(n2) (D) O(log2n)

3. 两个字符串相等的充要条件是（ ）。

(A)两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等

(C)同时具备(A)和(B)两个条件 (D)以上答案都不对

4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。

(A)99 (B) 97 (C) 91 (D) 93

5. 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。

(A)O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)

设有顺序排列的数组A从索引1到14共包含14个元素，在执行二分法查找目标值A[4]时，每次比较的具体过程是：依次进行中间项与目标值的比较、左半部分中间项与目标值的比较、右半部分中间项与目标值的比较。其中每次比较的具体步骤是什么？

(A)A[1]，A[2]，A[3]，A[4] (B)A[1]，A[14]，A[7]，A[4]

(C)A[7]，A[3]，A[5]，A[4] (D)A[7]，A[5] ，A[3]，A[4]

7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。

(A)8 (B) 7 (C) 6 (D) 5

8. 设一棵三叉树中包含2个度数为1的节点、2个度数为2的节点以及2个度数为3的节点，则其中该三叉链权中包含（ ）个度数为0的节点。

(A)5 (B) 6 (C) 7 (D) 8

确定无向图G中所有边的连接系统E={ (a,b), (a,e), (a,c), (b,e), (e,d), (d,f), (f,c) }后，则从顶点a出发采用广度/深度优先搜索方法可能得到的一种顶点路径为（ ）。

(A) aedfcb (B) acfebd (C)aebcfd (D) aedfbc

10. 队列是一种（ ）的线性表。

(A)先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除

---

二、判断题(20分)

当两个键的值不同时却其哈希函数返回相同的值，则我们称这两个键为互为同义词。（情况）

2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ）

3. 分块查找的核心概念在于首先在索引表中执行查找操作, 以便确定给定的关键字可能存在的块号, 并随后依次在对应的相关块内展开顺序查找。

4. 二维数组和多维数组均不是特殊的线性结构。（ ）

在某些情况下，在向二叉排序树中插入一个节点时所需进行的比较次数可能会超过该二叉树的高度。

6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ）

7. 非空的双向循环链表中任何结点的前驱指针均不为空。（ ）

无论线性表采用顺序存储结构还是链式存储结构，在其删除操作的时间复杂度皆为O(n)。

图的深度优先遍历算法中必须设置一个标志数组以标识哪些顶点已被访问过。（ ）

10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（ ）

---

三、填空题(30分)

给定一组初始记录关键字序列(49, 38, 65, 97, 76, 13, 27, 50)，经过一次希尔排序（步长d=4）后得到的结果是什么？

2． 下面程序段的功能用于实现二叉排序树中插入一个新结点，请将正确的填充内容填入下划线处。

该类型是一种二叉树数据结构定义。
结构体node包含三个成员：
- 数据成员data类型的字段
- 指针域lchild表示该节点的左子树
- 指针域rchild表示该节点的右子树
所有指针域均为指向同类node类型的指针变量。

void bstinsert(bitree *&t,int k)

{

if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;}

else if(t->data>k) bstinsert(t->lchild,k);else__________________________;

}

设指针变量p指示单链表中的节点A, 指针变量s指示待插入节点X, 则在节点A之后进行节点X的插入操作所需执行的操作序列为: s->next = p->next; 初始化为空;

4． 设为头结点的表示符head用于指示双向链表的第一个节点位置，并用指针变量p表示该链表的第一个实际数据节点，则有p = head 和 head = p（其中每个节点的两个链接域分别设为llink和rlink）。

给定一棵二叉树,其中缀周游序列是ABCD,后缀周游序列是BADC,那么它的前缀周游序列是什么呢?

6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

在给定一个有向图的情况下，并且该图不包含有向边(Vi, Vj)，那么该图所对应的邻接矩阵A中相应位置(i,j)处的数值为多少。

8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。

9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。

设有一组初始记录关键字序列为(50, 16, 23, 68, 94, 70, 73)，则将它们构建为初始堆结构仅需将16与其相应的元素进行互换位置即可

---

四、算法设计题(20分)

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

参考答案

一、选择题

1．C 2．C 3．C 4．B 5．B

6．C 7．B 8．C 9．A 10．A

二、判断题

1．对 2．错 3．对 4．错 5．错

6．对 7．对 8．对 9．对 10．对

三、填空题

1. (49，13，27，50，76，38，65，97)

2. t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)

3. p->next=s

4. head->rlink，p->llink

5. CABD

6. 1，16

7. 0

8. (13，27，38，50，76，49，65，97)

9. n-1

10. 50

四、算法设计题

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

voidcountnode(bitree *bt,int &count)

{

if(bt!=0)

{count++;countnode(bt->lchild,count); countnode(bt->rchild,count);}

}

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct {intvertex[m]; int edge[m][m];}gadjmatrix;

定义了一个GLinkNode类型的节点，
包含三个字段：
int infoField用于存储信息，
int adjVertex表示邻接顶点，
struct GLinkNode* nextArc指向前驱节点。
这样的节点组成了一个GLinkListNode链表结构。

在C语言中将实例化为名称的结构体定义为glinkheadnode

voidadjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ])

{

int i,j;glinklistnode *p;

for(i=0;i<=n-1;i++)g2[i].firstarc=0;

for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)

if(g1.edge[i][j]==1)

{

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;

p->nextarc=g[i].firstarc;g[i].firstarc=p;

p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;

p->nextarc=g[j].firstarc;g[j].firstarc=p;

}

}