《数据结构》试卷（A）
学    号：              姓  名：            日期：       
题  号
一
二
三
四
五
总  分
得  分
一、选择题（每小题2分，共30分，请写在答卷纸上）：
1.下列程序段的时间复杂度为（  ）。
i=0，s=0；
while (s<n) {s=s+i；i++；}
A. O(n1/2)    B. O(n1/3)    C. O(n)    D. O(n2)
2.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称
为（ ）。
A.树状结构      B.网状结构        C.线性结构        D.层次结构
3.在带有头结点的单链表head中，要向表头插入一个由指针p指向的结点，则执行(  )。
A. p->next=head; head=p;      B. p->next=head->next; head先序中序后序遍历二叉树->next=p;
C. p->next=head; p=head;      D. head=p; p->next=head;
4.一个栈的输入序列为a b c，则下列序列中不可能是栈的输出序列的是(  )。
A. b c a        B. c b a         C. c a b            D. a b c
5.无向完全图G有n个结点，则它的边的总数为（  ）。
A.n2            B.n(n-1)          C.n(n-1)/2        D.(n-1)
6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（   ）。
A.9              B.11            C.15                D.不确定
7.设连通图G中的边集E={(a,b),(a,c),(a,e),(b,e),(d,e),(d,f),(e,f)}，则在下面的4个序列中，不符合深度优先遍历的序列是（   ）。
A.acfdeb        B.aebdfc        C.aedfbc            D.aefdbc
8.队列是一种（  ）的线性表。
A.先进先出    B.先进后出    C.只能插入    D.只能删除
9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（   ）。
A.按层遍历      B.先序遍历          C.中序遍历        D.后序遍历
10. 设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i
结点的左孩子结点的编号为（  ）。
A. 2i+1    B. 2i    C. i/2    D. 2i-1
11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，
7，15)，则采用的排序方法是（  ）。
A.选择            B.快速          C.希尔            D.冒泡
12.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查，则查A［3］的比较序列的下标依次为(      )
A. 1，2，3        B. 9，5，2，3      C. 9，5，3            D. 9，4，2，3
13.设顺序循环队列Q[M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的当前位置，尾指针R总是指向队尾元素的后一位置，则该循环队列中的元素个数为（  ）。
A.R-F          B.F-R      C.(R-F+M)％M          D.(F-R+M)％M
14.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到
连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]
的地址之差为（  ）。
A.10          B.19        C.28          D.55
15.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（ ）。
A.p -> data = - 1    B.p -> next = NULL
C.p -> next -> next=head    D.p -> next = head
二．填空（每题2分，共22分，请写在答卷纸上）
1.数据元素之间的关系在计算机中有两种不同的表示方法: 【 】和【 】。
2.线性表L=(a1,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是【 】。
3.一个中缀算术表达式为（A+B）/C-D*(E-F)，其对应的后缀表达式为【 】。
4.设一棵完全二叉树中有500个结点，则该二叉树的深度为【 】；若用二叉链表作为该完全二叉树的存储结构，则共有【 】个空指针域。
5.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为【 】个，树的深度为【 】，树的度为【 】。
6.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是【 】。
7.设有向图G中有向边的集合E={<v1,v2>,<v1,v3>,<v2,v5>,<v2,v6>,<v3,v5>,<v3,v6>,
<v5,v4>,<v6,v4>>>}，则该图两个拓扑排序序列分别为【 】和【 】。
8.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为【 】。
9.已知广义表A=(x，((a，b)，c))，函数GetHead(GetHead(GetTail(A)))的运算结果是【 】。
10. 一个队列的入队序列是1234，则出队序列是【4】。
11. 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为【4】。
三、判断题（每小题1 分，共10分，请写在答卷纸上）
1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（  ）
2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（  ）
3．分块查的基本思想是首先在索引表中进行查，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查。（  ）
4．带权无向图的最小生成树是唯一的。（  ）
5．哈夫曼树中没有度数为1的结点。（  ）
6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（  ）
7．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（  ）
8．由树转化成二叉树，该二叉树的右子树不一定为空。（  ）
9．线性表中的所有元素都有一个前驱元素和后继元素。（  ）
10. 完全二叉树中的叶子结点只可能在最后两层中出现。（  ）
四、应用题（每题6 分，共30分）
1.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
void bubble(int r[n])
{
for(i=1;i<=n-1; i++)
{
for(exchange=0,j=0; j<_____________;j++)
if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}
if (exchange==0) return；
}
}
2.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。
初始堆：
第一趟：
第二趟：
3.设散列函数为H (key)=key ％ 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。
4.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，要求:
(1)画出此二叉树;
(2)给出后序遍历序列;
(3)画出中序前驱线索二叉树。
5.下图所示的森林： 
(1) 求树（a）的先根序列和后根序列；
(2) 求森林先序序列和中序序列；
(3)将此森林转换为相应的二叉树。
   
五、算法设计（共8分）
1.假设以单链表表示线性表，单链表的类型定义如下：
typedef struct node {
DataType data；
Struct node  *next；
} LinkNode，* LinkList；
设计判断单链表中元素是否是递增的算法。
参考答案
一、选择题（每小题2 分，共30分）
题号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
答案
A
A
B
C
C
B
A
A
C
B
C
D
C
B
D
二、填空题（每小题2分，共22分）
1
顺序映像
非顺序映像
2
(n-1)/2
3
AB+C/DEF-*-
4
9
500
5
9
3
3
6
69
7
V1,V2,V3,V6,V5,V4
或V1,V2,V3,V5,V6,V4
V1,V3,V2,V6,V5,V4
或V1,V3,V2,V5,V6,V4
8
40,38,46,56,79,84
9
(a,b)
10
1234
11
8
三、判断题（每小题1分，共10分）
题号
1
2
3
4
5
6
7
8
9
10
答案
Y
Y
Y
N
Y
Y
Y
N
N
Y
四.应用题
1.答: n-i    r[j+1]=r[j]
2. 解: 初始堆: 7, 14, 13, 26, 18, 45, 60, 32
      第一趟: 32, 14, 13, 26, 18, 45, 60, 7
      第二趟: 60, 14, 32, 26, 18, 45, 13, 7
3. 解: 
  0  1  2  3  4  5  6  7  8  9  10
 
  55  43  13  24      27  49  18  38      32
 
4.解: (1) 二叉树如下:
     
    (2) 后序遍历序列为CDBGFEA
    (3) 中序前驱线索二叉树如下:
       
 
5.解: (1)先根序列：ABCDEF  后跟序列：BDEFCA

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。