《数据结构问题》由会员分享，可在线阅读，更多相关《数据结构问题（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构问题试卷 选择10.一组记录的排序码为(25, 48, 16, 35, 79, 82, 23, 40, 36, 72),其中含有5个长度为 2 的有序表,按归并排序的方法对该序列进行一趟归并后的结果为.A.16,25,35,48,23,40,79,82,36,72B.16,25,35,48,79,82,23,36,40,72C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82填空4假设在有序线性表A1.20上进行折半查找，平均查找长度约为。简答4.已知一组关键字为(10, 24, 32, 17, 31, 30, 4
2、6, 47, 40, 63, 49),设哈希函数H (key)=key % 7。请解答：(1) 写出用链地址法处理冲突构造所得的哈希表；(2) 若查找关键字 31,需要依次与哪些关键字进行比较？(3) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。试卷二 选择3. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3,当 从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少。A. 1 和 5 B. 2 和 4C. 4 和 2D. 5 和 14设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a为第一元素，其11存储地址为
3、1,每个元素占一个地址空间，则a85的地址为。A.13B.33C.18D.404.在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时,当把第 7 个记录60插入到有序表时，为寻找插入位置需比 次。简答4. 有一个1000项的表,要分块查找(索引表也是顺序查找),试问：(1) 最理想分多少块和每块最理想长度是多少?求此时的 ASL。(2)若每块是 10, ASL 是多少？Ik试卷三3. 若以4, 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是.5一组记录的排序码为(45, 29, 56, 37, 40, 84, 82),
4、则利用堆排序的方法建立的初始 堆(大顶堆)为。(要求写出序列而不要画出图形)试卷五选择4. 若串 S = ABCDEFG , S2= 9898,S3= # ,S4= 012345，执行1concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2,8 ),length(S2)，其结果为()。A. ABC#G0123 B. ABCD#2345 C. ABC#G1234 D. ABCD#12348.当采用分快查找时，数据的组织方式为 （）。A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序
5、，但块间必须有序，每块内最大（或最小）的数据 组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左 孩子的平衡因子为0右孩子的平衡因子为1,则应作（ ） 型调整以使其平衡。（平衡因子= 左子树深度-右子树深度）A. LL （单向右旋）B. LR （先左后右双向旋转）C. RL （先右后左双向旋转）D. RR （单向左旋）填空4.当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为。简答3. 设有正文 AADBAACA
6、CCDACACAAD, 字符集为 A,B,C,D, 设计一套二进制哈夫曼编码，使得上述 正文的编码最短。（求解过程中要求画出编码树）试卷六 选择&在等概率情况下,线性表的顺序查找的平均查找长度ASL为（1）,有序表的折半查找 的ASL为（2），对二叉排序树表,在最坏情况下,ASL为（3），而当它是一棵平衡树时,ASL 为 ( 4)）。A.(1)( 2)( 3)( 4)B.(1)( 2)( 3)( 4)C.(1)( 2)( 3)( 4)D.(1)( 2)( 3)( 4)O (1) ,O(n),O(n),O(n),供选择的答案：O(n)O(log）。, O(log n) , O(n log n)2
7、2O(nlog n) , O(1)2O (log n )2, O ( n ) , O (log n )2O(log n) , O(n) , O(n log n)22填空2. n阶上二角矩阵A （当ij时，有a . = 0 , 1 i, j n）压缩的下标对应关系为：。j3. 若a=1，b=2， c=3, d=4,则后缀式db/cc*a-b*+的运算结果为。试卷七填空2.一棵二叉树有67个结点,这些结点的度要么是0，要么是2。这棵二叉树中度数为2的结点 有个。3线性表L=（al,a2,a采用顺序结构存储，假定在不同的位置上插入的概率相同，则插入一 个新元素平均需要移动的元素个数是。4. 栈S和队
8、列Q的初始状态皆为空，元素al,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳个元素。简答5设散列表为HT13,散列函数为H （key） = key %13。用闭散列法解决冲突，对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1)采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均 搜索长度和搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) %
9、10 + 1, 寻找下一个 空位的公式为H. = (H+ RH (key) % 13, H, = H (key)。画出相应的散列表，并计算等概率下ii-11搜索成功的平均搜索长度。试卷十选择4. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表25.当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是()。n乙Ai,刀为 A b,jn乙 A j, iA i=1B j=1Ci=15 .下列程序判断字符串s是否对称，对称则返回1否则返回0；如f(abba)返回1 f(abab)返回 0；int f(
10、 _) int i=0,j=0;while (sj)_ ;for(j-; ij & si=sj; i+,j-);return(_ _)练习题 8查找填空6已知有序表为(12，18， 24，35，47，50，62，83，90，115，134)，当用折半查找 90时，需进行次查找可确定成功；查找47时，需进行次查找成功；查找100时, 需进行 次查找才能确定不成功。练习题9排序 选择4. 一组记录的排序码为(46， 79， 56， 38， 40， 84)，则利用堆排序的方法建立的初始堆为A. 79， 46， 56， 38， 40， 84C. 84， 79， 56， 38， 40， 465. 一组记
11、录的关键码为(46， 79， 56B. 38， 46, 56， 79， 40， 84D. 84， 56， 79， 40， 46， 3838， 40， 84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A. 38，40，46，56，79，84B. 40，38，46，79，56，84C. 40，38，46，56，79，84D. 40，38，46，84，56，799. 用某种排序方法对线性表( 25， 84， 21， 47， 15， 27， 68， 35， 20)进行排序时，元素 序列的变化情况如下： 25，84，21，47，15，27，68，35，20 20，15，21 ，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20， 21，25，27，35 ，47，68，84综合1. 以关键码序列(265,301,751,129 ,937,863,742,694 ,076,438)，为例，手工执行以下 排序算法，写出每一趟排序结束时的关键码状态：1)直接插入排序；2)希尔排序3)冒泡排序4)快速排序；5)直接选择排序6)堆排序；7)归并排序；(8)基数排序
