《算法与数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《算法与数据结构试题及答案.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构模拟试题.。一、简答题（15 分,每小题 3 分）1.简要说明算法与程序的区别。2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么?3.说明在图的遍历中，设置访问标志数组的作用。4.说明以下三个概念的关系：头指针,头结点，首元素结点。5.在一般的顺序队列中，什么是假溢出?怎样解决假溢出问题?二、判断题(10 分,每小题 1 分）正确在括号内打，错误打(）(1）广义表（(a)，b),c)的表头是（a)，b）,表尾是（c）。（)（2）在哈夫曼树中，权值最小的结点离根结点最近。（）(3)基数排序是高位优先排序法。（）（4)在平衡二叉树中,任意结点左右子树的高度差（绝对值）不超过 1。（）
2、(5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s 插入结点 p 的后面:p-next=s；s-next=p-next；()（6）抽象数据类型（ADT)包括定义和实现两方面，其中定义是独立于实现的,定义仅给出一个ADT 的逻辑特性，不必考虑如何在计算机中实现.（）（7)数组元素的下标值越大,存取时间越长。()（8)用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（)(9）拓扑排序是按 AOE 网中每个结点事件的最早发生时间对结点进行排序。()(10）长度为 1 的串等价于一个字符型常量。三、单项选择题（10 分，每小
3、题 1 分）1排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序2已知一个有向图的邻接矩阵表示，要删除所有从第 i 个结点发出的边，应该：A）将邻接矩阵的第 i 行删除 B）将邻接矩阵的第 i 行元素全部置为 0C)将邻接矩阵的第 i 列删除 D）将邻接矩阵的第 i 列元素全部置为 03有一个含头结点的双向循环链表，头指针为 head,则其为空的条件是：A.headpriro=NULL B。head-next=NULLC.head-next=head D.headnext-priro=N
4、ULL4。在顺序表（3,6,8,10,12，15,16,18,21,25，30)中,用折半法查找关键码值 11，所需的关键码比较次数为:A)2 B）3 C)4 D)55.以下哪一个不是队列的基本运算？A）从队尾插入一个新元素 B）从队列中删除第 i 个元素 C)判断一个队列是否为空 D）读取队头元素的值6.在长度为 n 的顺序表的第 i 个位置上插入一个元素(1 i n+1），元素的移动次数为:A)n i+1 B）n i C)i D)i 17对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:A）顺序表B）用头指针表示的循环单链表 C)用尾指针表示的循环单链表 D)单链表8对包含
5、n 个元素的哈希表进行查找，平均查找长度为：A)O(log2n）B)O(n)C)O（nlog2n)D）不直接依赖于 n9将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号,根结点编号为 1，则编号最大的非叶结点的编号为：A、48B、49C、50D、5110某二叉树结点的中序序列为 A、B、C、D、E、F、G，后序序列为 B、D、C、A、F、G、E，则其左子树中结点数目为:A)3 B）2 C)4 D）5四、填空题（10 分,每空 1 分）1填空完成下面一趟快速排序算法：int QKPass（RecordType r ,int low,int high)x=r l
6、ow ；while(low high)while(low high&r.key=x。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 开始）,如果按“以列为主的顺序存储，则排在第
7、 8 个位置的元素是：5高度为 h 的完全二叉树最少有个结点.五、构造题（20 分)1（4 分）已知数据结构 DS 的定义如下，请给出其逻辑结构图示。DS=(D，R）D=a，b，c,d,e，f，g R=T T=，a,g,，,d,f，e，d，f，a，f,e,，g，d，2(6 分）对以下关键字序列建立哈希表：（SUN,MON，TUE，WED,THU，FRI，SAT)，哈希函数为 H（K)=(K 中最后一个字母在字母表中的序号)MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0。7 的哈希表，并计算出在等概率情况下查找成功的平均查找长度。3.（6 分）将关键字序列（3，26，12，61，38
8、，40,97,75，53，87）调整为大根堆。4（4 分）已知权值集合为：5，7，2，3，6，9 ，要求给出哈夫曼树，并计算其带权路径长度 WPL.六、算法分析题（10 分）阅读下面程序，并回答有关问题。其中 BSTree 为用二叉链表表示的二叉排序树类型。（1）简要说明程序功能。（5 分)（2）n 个结点的满二叉树的深度 h 是多少?（3 分）（3）假设二叉排序树*bst 是有 n 个结点的满二叉树,给出算法的时间复杂度。（2 分）int Proc（BSTree *bst,KeyType K）BSTree f，q，s;s=（BSTree）malloc（sizeof(BSTNode）)；s k
9、ey=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 key）f lchild=s；else f-rchild=s；return 1;七、算法设计题（25 分）1已知一个带头结点的整数单链表 L,要求将其拆分为一个正整数单链表 L1 和一个负整数单链表 L2.（9分）2无向图采用邻接表存储结构,编写算法输出图中各连通分量的结点序列。(8 分）3编写一个建立二叉树的算法，
10、要求采用二叉链表存储结构。（8 分）2002 级数据结构试卷参考答案与评分标准一、简答题（15 分，每小题 3 分）6.算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。7.主要与哈希函数、装填因子有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子较小，则哈希表较稀疏，发生冲突的可能性较小。8.图中结点可能有多个前驱,设置访问标志数组主要是为了避免重复访问同一个结点.9.头指针指向头结点，头结点的后继域指向首元素结点.10.当队尾到达数组最后一个单元时,就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是
11、采用循环队列,即令最后一个单元的后继是第一个单元。二、判断题(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）10C）四、填空题（10 分,每空 1 分）1highlowlowhigh2。S-next=R-next；Rnext=S ;3时间空间 4 A2，3 5 2h1五、构造题（20 分)1（4 分）01234567SUNMONTHUFRIWEDTUESAT2（6 分）ASLsucc=（14+22+3)/7=11/73。（6 分）894（4 分）已知权值集合为:5,7，2，3，6，9,要求给出哈夫曼树，并计算其带权路径长度 WPL。WPL=2(9+6+7）+35+4(2+3)=79六、算法分析题（10 分）解:（1）在二叉排序树中插入关键字为 K 的结点（2）h=log2（n+1)或 h=log2 n +1（方括号表示向下取整）（3）O（log2(n+1）)或 O(log2 n)七、算法设计题（25 分）（答案略）