适用专业： 0811 控制科学与工程、0854 电子信息
考试科目： 816 数据结构与算法A 卷
考试时间： 3 小时
、 选择题(每题 2 分， 共 60 分)
l、 下列不属千数据的存储结构的是( )。
A. 逻辑结构 B. 顺序存储结构 C. 链式存储结构 D. Hash 存储结构
2、 算法分析的两个主要方面是( )。
A. 正确性和简明性 B. 空间复杂度和时间复杂度
C. 可读性和文档性 D. 数据复杂性和程序复杂性
3、 下面关千算法说法错误的是( )。
A. 算法原地工作的含义是指不需要其他计算机辅助实现
B. 复杂度O(n)的算法在时间上不一定总是优千复杂度 O(n2 ) 的算法
C. 同一个算法，不同的程序员实现，用低级语言实现的效率不一定比高级语言实现效率高
D. 工程总不一定总是选择算法时间复杂度低的算法
4、 以下程序段的时间复杂度正确表示是( )。
for (i=l ;i
for (j=O; j<=(2*n); j++)
x++;
｝
A.0((2n)2) B. n*(n+l)/2 C. O(n2) D. 2n2
5、 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。
A. 仅有头指针的单循环链表 B. 仅有尾指针的单循环链表
C. 单链表 D. 双链表
6、 在表长为 n 的顺序表中， 算法时间复杂度为 0 (1)的操作为( )。
A. 在第 i 个元素前插入一个元素
B. 删除第 i 个元素
考试科目： 816 数据结构与--算--法-第 1 页 共 8
C. 查找其值与给定值相等的一个元素
D. 在表尾插入一个元素
7、 关千线性表下面的叙述正确的是( )。
A. 线性表在用单链表存储时， 查找第 i 个元素的时间同 i 的值成正比
B. 线性表 在顺序存储时， 查找第 i 个元素的时间同 i 的值成正比
C. 线性表在顺序存储时 ， 查找第 i 个元素的时间同第 i 个元素的概率成正比
D. 线性表在 用循环双链表存储时， 查找第 i 个元素的时间比数组快
8、 对于顺序表， 以下说法错误的是( )。
A. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
B. 顺序表的特点是：可以随机存取元素
C. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
D. 顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中
9、 顺序表的插入算法中 ， 当 n 个空间已满时， 可再申请增加分配 m 个空间， 若申请失败，则说明系统没有( )可分配的存储空间。
A.n+m 个 B. n+m 个连续 C. m 个 D. n+ l 个离散
10、 设有一个栈， 元素依次进栈的顺序为 A、B、C、D、E。 下列( )是不可能的出栈序列。
A. E,A,B,C,D B. A,B,C,D,E C. B,C,D,E,A D. E,D,C,B,A
11、 在循环队列中， 若 front 与 rear 分别表示对头元素和队尾元素的位置 ， 则判断循环队列空的条件是( )。
A. front==O
C. rear==front+ IB. front==rear+ I
D. front==rear
12、 对 5 个不同的数据元素进行直接插入排序 ， 最多需要进行的比较次数是( )。
A.8 B.10 C. 15 D.25
13、 在原始记录基本有序时 ， 以下说法正确的是( )。
A.对冒泡排序没有影响 B.对直接插入排序没有影响
C对直接选择排序没有影响 D对 Shell 排序没有影响
14、 设有两个串 p 和 q, 其中 q 是 p 的子串， 求 q 在 p 中首次出现的位置的算法称为()。
A.求子串 B串 联接 C串匹配 D.求串长
15、 设有一个二维数组 A[m][n], 设 A[O][O] 存放位置在 644 , A[2][2]存放位置在 676 ,每个元素占一个空间 ， 问 A[3][3]存放在( )位置。
A.692 B.693 C.689 D.690
16、 若一棵二叉树具有 10 个度为 2 的结点， 5 个度为 1 的结点， 则度为 0 的结点个考试科目： 816 数据结构与算法 第 2 页 共 8 页
、J
数是( )。
A.9 B.11 C.15 D.不确定
17、 对具有 1000 个结点的完全二叉树按从上到下、从左到右的顺序依次编号 1, 2,3, …， N, 则第 501 个结点的双亲结点编号为 ：( )。
A.250 B.251 C.500 D.不确定
18、 利用二叉链表存储树 ， 则根结点的右指针是( )。
A 指向最左孩子 B指向最右孩子 C空
19、 在下列存储形式中 ，( )不是树的存储形式?
A双 亲表示法 B孩 子链表表示法
C孩子兄弟表示法 D顺序存储表示法D.不确定
20、 设 F 是一个森林 ， B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点， 则 B中右指针域为空的结点有( )个。
A.n-1 B.n C.n+l D.n+2
21、 若一棵二叉树的前序遍历序列和后序遍历序列分别为 abed 和dcba, 则该二叉树的中序遍历序列不会是( )。
A.abed B.bcda C.cbda D.dcba
22、 一个有 N 个顶点和 N 条边的无向图， 一定是( )。
A连 通的 B.不连通的 C无 环的 D有 环的
23、 若图的邻接矩阵中主对角线上的元素全是 0 ' 其余元素全是 1 ' 则可以断定该图一定( )。
A是 无向图 B不 是带权图
C是 有向图 D是 完全图
24、 邻接矩阵是对称矩阵的图为( )。
A有 向网 B无 向网
C有向网和无向网都是 D有向网和无向网都不是
25、 用邻接表存储的图的深度优先遍历算法，类似于树的( )。
A.中序遍历 B先序遍历 C后序遍历 D按层次遍历
26、 任何一个无向连通图的最小生成树( )。
A有 一棵或多棵 B只 有一棵 C.一定有多棵 D.可能不存在
27、 折半查找和二叉排序树查找的时间 性能()。
A相 同 B有 时不同 C完 全不同 D无 法比较
28、 散列 ( Hash ) 查找一般适用于( )情况下的查找。
A查找表为链表
B. 查找表为有序表
C 关键字集合比地址集合大得多
D关键字集合与地址集合之间存在对应关系
29、 假设有 K 个关键字互为同义词， 若用线性探查法把这 k 个关键字存入 ， 至少要进行的探查次数是( )。
A.k-1 B.k C.k+l D.k(k+l)/2
30、 在采用链地址法处理冲突所构成的散列表上查找某一个关键字 ， 则查找成功的情况下，所探测的这些位置上的键值( )。
A.一定都是同义词 B不 一定都是同义词
C都 相同 D.一定都不是同义词
二、填空题(每空2 分， 共 28 分)
l、 双链表的两个域分别是 prior 和 next, 完成在双循环链表结点 p 之前插入 s 的操作是(不填分号) ; s->next=p; p->prior=s;
2、 对于一个以顺序实现的循环队列 Q[O… m-1] , 队首、队尾指针分别为Q.f 和 Q.r,
其队列长度是 (Q 为队列变量)
3、 一组记录的关键码为 C 36,29,38,18,39,20,36,64), 则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 ， dk=3 的第一趟希尔排序结果为
4、 已知广义表为 D=(a,(b,0 ,c),((d),e)),该表的长度为 。
5、 由 3 个结点可以构造出 种不同的二叉树。
6、 深度为 h 的满 m 叉树的第 k 层有 个结点。(l =
7、 设有 5 个结点的权值分别为 3,4,5,6,7, 根据这些权值构造一棵 Huffman 树， 则该树的带权路径长度 WPL 为 。
8、 已知一棵完全二叉树的第 7 层(设根为第 1 层)有 8 个叶子结点， 则该完全二叉树的结点个数最少是
9、 在有 N(N> l )个顶点的有向图中 ， 每个顶点的度最大可达 。
10、 假设一个图有 n 个顶点、e 条边， 则在最小生成树算法中， 普利姆(prim) 算法的时间复杂度为 ，因此适合用于求 (选填稀疏、稠密)图的最小生成树。
11、 对于长度为 10 的有序顺序表， 若查找每个元素的概率相等 ， 则用折半查找法查找顺序表中任意元素的查找成功的平均查找长度为 (保留一位小数)。
三、程序填空题(每空 3 分， 共 42 分)
l 、 在顺序线性表 L 中删除第i 个元素 ( I <=i), 并用 e 返回其值。完成该算法。
typedef struct {
ElemType *elem; //存储空间基址
int length; II当前长度
int listsize;II当前分配的存储容量
} SqList;
Status ListDelete_sq(SqList &L, int i, ElemType &e) {
if (i < I II— ( I ) —— ) return ERROR; II i 值合法性判断
e=L.elem[i-1]; II 被删元素的值赋给e forG=i; —( 2) — ; j++)
— ( 3) — =L.elem 廿];
--L.length;
return OK;
｝
2、 已知单链表的表首指针为 head , 下面的函数 de lete 是从单链表中删除指针为 p的结点(假定单链表中一定存在被删结点)，并返回新的表首指针。请完成如下程序：
3、 用栈实现判断回文数，填空；
栈的操作函数如下：
将 x 入栈 s: push(s,x); 出栈，并赋值给 x:
4、 直接插入排序算法实现填空
5、 以二叉链表作为二叉树的存储结构，编写算法交换二叉树每个结点的左孩子和
右孩子。
(说明：对任何非叶子结点，要求先访问左子树，后访问右子树)
void ChangeLR(BiTree &T)
{
BiTree temp;
考试科目： 816 数据结构与算法 第 6 页 共 8 页
V
if(T==NULL) II 若为空树
return;
if(T->lchild==NULL & & — ( I ) — ) II 若为叶子结点
return;
else
{
temp= T->lchild;
T->lchild = T->rchild; T->rchild = temp;
｝II 交换
ChangeLR(_ ( 2) —-—;)
ChangeLR( 代码与 ( 2 ) 类似 );
｝
自顶点 l 出发进行深度优先遍历所得的遍历序列是： (I)
自顶点 1 出发进行广度优先遍历所得的遍历序列是 ： (2)
((1) (2) 问答题说明： 小序号优先原则， 无需任何分隔符)
请在答题纸上绘制该图的逆邻接表。 (3)
3、(共8 分)从空树开始依次插入如下元素{7, 3, 5, 15, 11, I, 9, 13}, 建立一棵排序二叉树。
( 1 ) 请在答题纸上画该排序二叉树。
( 2 ) 该二叉树是否为平衡二叉树?
( 3 ) 若查找 12, 将依次哪些元素比较?
( 4) 计算查找成功的平均查找长度和查找不成功的平均查找长度。
