数据结构期中测试 - 在线考试测评模板

Q1:姓名

A1

Q2:学号

A1

:一、单项选择题:（每小题3分，本大题共60分）

Q3:一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是（）

A. 108

B. 100

C. 110

D. 120

Q4:在一个长度为n的顺序表中第i个位置插入一个元素的算法时间复杂度为（）。

A. O(1)

B. O(n)

C. O(n2)

D. O(n3)

Q5:将一个由指针p所指向的结点插入到单链表L中由指针q所指向的结点后面，则需要执行的语句为（）。

A. p->next = q->next; q->next = p;

B. q->next = p; p->next = q->next;

C. p->next = q->next; q = p;

D. q->next = p->next; p->next = q;

Q6:一般计算机提交打印作业的速度比打印机打印的速度要快很多，为了解决速度不匹配问题，需要在计算机中设置一个打印缓冲区。打印缓冲区的实现一般采用（）。

A. 栈

B. 数组

C. 队列

D. 广义表

Q7:用链表表示线性表的优点是（）。

A. 便于随机存取

B. 花费的存储空间比顺序表少

C. 便于插入与删除

D. 数据元素的物理顺序与逻辑顺序相同

Q8:使用一维数组压缩存储n阶上三角矩阵时，常数c在一维数组中的索引位置为（）。

A. 0

B. 1

C. n(n+1)/2-1

D. n(n+1)/2

Q9:设有串t=”computer software”，那么Substring(t,6,6)=（）。

A. comput

B. softwa

C. ter so

D. ter sof

Q10:一个广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。

A. d

B. (d)

C. c

D. (g)

Q11:利用孩子-兄弟法表示树时，其二叉链表的根结点的右指针是（）。

A. 树的根结点的最左孩子

B. 树的根结点的最右孩子

C. 空

D. 非空

Q12:若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。

A. 9

B. 11

C. 15

D. 不确定

Q13:设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A. M1

B. M3

C. M1+M2

D. M2+M3

Q14:头指针为head的带头结点的单链表为空的判定条件是（）。

A. head==NULL

B. head!=NULL

C. head->next==head

D. head->next==NULL

Q15:在大小为 size 的循环队列中，队列满的判定条件是（）

A. rear=front-1

B. front=(rear+1)%size

C. rear=(front+1)%size

D. front=rear

Q16:广义表 G=(a,G) 的深度是（）。

A. 1

B. 2

C. 无穷

D. 0

Q17:树的后根遍历结果与其孩子-兄弟法所表示的二叉树的后序遍历结果是一样的,这种说法是（）。

A. 错误的

B. 正确的

C. 不确定

D. 以上答案都不对

Q18:深度为k的完全二叉树若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（）。

A. 2的k-2次方 - 1

B. 2的k-2次方 +1

C. 2的k-1次方

D. 2的k-1次方 - 1

Q19:某二叉树的先序遍历结点访问顺序是ABDGCEFH，中序遍历的结点访问顺序是DGBAECHF，则其后序遍历的结点访问顺序是（）。

A. BDGCEFHA

B. GDBECFHA

C. BDGAECHF

D. GDBEHFCA

Q20:已知某二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，它的先序遍历序列是（）。

A. ACBED

B. DECAB

C. DEABC

D. CEDBA

Q21:设一棵完全二叉树中有999个节点，用二叉链表做存储结构，则有多少个空指针域（）。

A. 1000

B. 999

C. 1200

D.1998

Q22:20、已知一棵完全二叉树共有50个结点，则叶子结点的个数为（）。

A. 19

B. 20

C. 25

D. 30

:二、简答题:（本大题共20分）

Q23:已知一个6*5稀疏矩阵如图所示，试采用三元组表作为存储结构，写出它的行优先三元组线性表（5分）。[图片]

选项1

Q24:请画出下列森林对应的二叉树。（5分）[图片]

选项1

Q25:假定用于通信的电文由5个字母A、B、C、D、E组成，若电文为“ADCEBDBCACADEEEEDAED”，试通过构造最优二叉树求出每个字符的Huffman编码。要求：（1）画出构造的Huffman树。（5分）（2）计算树的带权路径长度WPL。（2分）（2）给出每个字符的编码。（3分）

选项1

:三、算法设计题:（本大题共20分）

Q26:简要说明下列算法的主要功能。（5分）[图片]

选项1

Q27:有一个线性表(a1，a2，…，an)，它存储在带有表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号。如果x不存在，则输出序号为0。（15分）

选项1