数据结构模拟试题...
一、简答题15分,每小题3分
1.简要说明算法与程序的区别;
2.在哈希表中,发生冲突的可能性与哪些因素有关为什么
3.
4.说明在图的遍历中,设置访问标志数组的作用;
5.说明以下三个概念的关系：头指针,头结点,首元素结点;
6.在一般的顺序队列中,什么是假溢出怎样解决假溢出问题
7.
二、判断题10分,每小题1分
正确在括号内打√,错误打×
1广义表 a , b, c 的表头是 a , b,表尾是 c ;
2在哈夫曼树中,权值最小的结点离根结点最近;
3基数排序是高位优先排序法;
4在平衡二叉树中,任意结点左右子树的高度差绝对值不超过1;
5在单链表中,给定任一结点的地址p,则可用下述语句将新结点s插入结点p的后面 ：p->next = s; s->next = p->next;
6抽象数据类型ADT包括定义和实现两方面,其中定义是独立于实现的,定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现;
7数组元素的下标值越大,存取时间越长;
8用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中结点个数有关,而与图的边数无关;
9拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序;
10长度为1的串等价于一个字符型常量;
三、单项选择题10分, 每小题1分
1．排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置;这是哪种排序方法的基本思想
A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序
2． 已知一个有向图的邻接矩阵表示,要删除所有从第i个结点发出的边,应该：
A将邻接矩阵的第i行删除 B将邻接矩阵的第i行元素全部置为0
C将邻接矩阵的第i列删除 D将邻接矩阵的第i列元素全部置为0
3．有一个含头结点的双向循环链表,头指针为head, 则其为空的条件是：
A. head->priro==NULL B. head->next==NULL
C. head->next==head D. head->next-> priro==NULL
4. 在顺序表 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 中,用折半法查关键码值11,所需的关键码比较次数为：
A 2 B 3 C 4 D 5
5. 以下哪一个不是队列的基本运算
A从队尾插入一个新元素 B从队列中删除第i个元素
C判断一个队列是否为空 D读取队头元素的值
6. 在长度为n的顺序表的第i个位置上插入一个元素1≤ i ≤n+1,元素的移动次数为：
A n – i + 1 B n – i C i D i – 1
7．对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为:
A 顺序表 B 用头指针表示的循环单链表
C 用尾指针表示的循环单链表 D 单链表
8．对包含n个元素的哈希表进行查,平均查长度为：
A Olog2n B On C Onlog2n D 不直接依赖于n
9．将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点
进行编号,根结点编号为1,则编号最大的非叶结点的编号为：
A、48 B、49 C、50 D、51
10．某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、E,则其左子树中结点数目为：
A3 B2 C4 D5
四、填空题10分,每空1分
1．填空完成下面一趟快速排序算法：
int QKPass RecordType r , int low, int high
{ x = r low ；
while low < high
{
while low < high && r . key >=
high - -；
if low < high
{ r = r high ； low++; }
while low < high && r . key < x. key
low++;
if low < high
{ r = r low ； high--; }
}
r low = x； return low ;
}
2. 假设用循环单链表实现队列,若队列非空,且队尾指针为R, 则将新结点S加入队列时,需执行下面语句： ； ；R=S；
3．通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣;
4．已知一个3行、4列的二维数组A各维下标均从1开始,如果按“以列为主”的顺序存储,则排在第8个位置的元素是：
5．高度为h的完全二叉树最少有 个结点;
五、构造题20 分
1．4分已知数据结构DS的定义如下,请给出其逻辑结构图示;数组和链表
DS = D, R
D = { a, b, c, d, e, f, g }
R = { T }
T = { <a, b>, <a, g>, <b, g>, <c, b>, <d, c>, <d, f>,
<e, d>, <f, a>, <f, e>, <g, c>, <g, d>, <g, f> }
2．6分对以下关键字序列建立哈希表：SUN, MON, TUE, WED, THU, FRI, SAT,哈希函数为HK =K中最后一个字母在字母表中的序号MOD 7;用线性探测法处理冲突,要求构造一个装填因子为的哈希表,并计算出在等概率情况下查成功的平均查长度;
3.6分将关键字序列3,26,12,61,38,40,97,75,53, 87调整为大根堆;
4．4分已知权值集合为：{ 5,7,2,3,6,9 },要求给出哈夫曼树,并计算其带权路径长度WPL;
六、算法分析题10分
阅读下面程序,并回答有关问题;其中BSTree为用二叉链表表示的二叉排序树类型;
（1）简要说明程序功能;5分
（2）n个结点的满二叉树的深度h是多少
（3）3分
（4）假设二叉排序树bst是有n个结点的满二叉树,给出算法的时间复杂度;2分
int Proc BSTree bst, KeyType K
{ BSTree f, q, s;
s=BSTreemallocsizeofBSTNode;
s-> key = K; s-> lchild = NULL; s-> rchild = NULL;
if bst == NULL { bst = s; return 1; }
f = NULL; q = bst;
while q = NULL
{ if K < q -> key
{ f = q; q = q -> lchild; }
else
{ f = q; q = q -> rchild; }
}
if K < f -> key f -> lchild = s;
else f -> rchild = s;
return 1;
}
七、算法设计题25分
1．已知一个带头结点的整数单链表L,要求将其拆分为一个正整数单链表L1和一个负整数单链表L2;9分
2．无向图采用邻接表存储结构,编写算法输出图中各连通分量的结点序列;8分
3．编写一个建立二叉树的算法,要求采用二叉链表存储结构;8分
2002级数据结构试卷参考答案与评分标准
一、简答题15分,每小题3分
8.算法是解决特定问题的操作序列,可以用多种方式描述;程序是算法在计算机中的实现,与具体的计算机语言有关;
9.主要与哈希函数、装填因子α有关;如果用哈希函数计算的地址分布均匀,则冲突的可能性较小,如果装填因子α较小,则哈希表较稀疏,发生冲突的可能性较小;
10.图中结点可能有多个前驱,设置访问标志数组主要是为了避免重复访问同一个结点;
11.头指针指向头结点,头结点的后继域指向首元素结点;
12.当队尾到达数组最后一个单元时,就认为队满,但此时数组前面可能还有空单元,因此叫假溢出;解决的方法是采用循环队列,即令最后一个单元的后继是第一个单元;
二、判断题10分,每小题1分
1√ 2× 3× 4√ 5×
6√ 7× 8√ 9× 10×
三、单项选择题10分, 每小题1分
1． D 2． B 3． C 4. C 5. B
6. A 7． C 8． D 9． C 10．C
四、填空题10分,每空1分
1． high low low high
2. S->next=R->next ； R->next=S ；
3． 时间 空间 4． A2, 3 5． 2h-1
五、构造题20 分
1．4分
2．6分
ASLsucc = 1×4 + 2×2 + 3 / 7 = 11 / 7
3.6分
4．4分已知权值集合为：{ 5,7,2,3,6,9 },要求给出哈夫曼树,并计算其带权路径长度WPL;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论