文件名称：数据结构题
文件大小：47KB
文件格式：DOC
更新时间：2016-01-17 10:45:20
数据结构题
一、选择 1.若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为( ) A.顺序存储结构 B.链式存储结构 C.线性存储结构 D.散列存储结构 2.在长度为100的顺序表的第10个位置上插入一个元素，元素的移动次数为( ) A.90 B.91 C.89 D.92 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表 4.若进栈序列为c， a，b，则通过入出栈操作可能得到的a,b,c的不同排列个数为( ) A.4 B.5 C.3 D.2 5.为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A.插入 B.删除 C.串联接 D.子串定位 7.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［2］[4][5]的存储地址为( ) A.296 B.298 C.300 D.302 6.下列陈述中正确的是( ) A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分 7.n个叶子的霍夫曼树结点总数为( ) A.2n B.2n-1 C.2n+1 D.不能确定 8.有向图的邻接矩阵中，每列元素之和为该顶点的( ) A.度 B.入度 C.出度 D.权值 9.100个结点完全二叉树高度是( ) A.9 B.10 C.11 D.12 10.n个顶点的无向完全图中含有向边的数目最多为( ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为( ) A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( ) A.快速排序 O(n*n) B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是( ) A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14.平衡二叉树中任一结点的( ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在VSAM文件的控制区间中，记录的存储方式为( ) A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 二、填空题 16.若一个算法中的语句频度为T(n)=3720n3/2+4nlogn，则算法的时间复杂度为________。 17.单链表中若在指针p所指的结点之后插入指针s所指结点，则可用下列两个语句实现该操作，是_s->next=p->next和_______ _。 18.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXXSSXX之后，得到的输出序列为________。 19.串S=″I am a worker″的长度是________。 20.假设一10阶下三角矩阵按列优顺序压缩存储一维数组C中，则C数组的大小为________。 21.在n个结点的二叉链表中，有________个空指针。 22.对关键字序列(52，80，63，44，48，21)进行一趟简单选择排序之后得到的结果为________。 23.由10个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________，最小为 。 24头指针为f，尾指针为r的循环队列判断空的条件是 (r+1)%max==f 。 三、问答题 1.已知一个6行5列的稀疏矩阵中非零元的值分别为：9，41，6，8，-54，5和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4和5,其行值依次为1，1，2，2，3和5。请写出该稀疏矩阵。 2.已知二叉树树T的先序遍历序列为ABCDE，中序遍历序列为CBDEA。请画出二叉树T。 3.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆：_94，87，。。。_______ 第1趟：{94}，87，72，61，58，23，16，5 第2趟：{94，87}，72，58，61，5， 23，16， 4.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值41相等的关键字，请写出查找过程中依次和给定值“41”比较的关键字。平均查找长度。 ASL=（1+2+3）/8= 霍夫曼树：给定若干关键字在某次通信中出现频率，要求构造霍夫曼树并求每个结点编码。a,b,c,d,e,f:2,5,7,8,12,30 关键字序列：4，7，11，14，49，54，散列函数H（key）=key%7，散列表长0。。6，线性探测法处理冲突，构造该散列表。 关键字序列： 14，7，11，4，49，54，写出直接插入排序，起泡排序，简单选择排序（快速排序）每趟结果。 初始序列:{14，7，11，4，49，54} 第一趟{4，7，11}，14，{49，54} 第二趟：4，{7，11}，14， 49，{54} 第三趟4，7，{11}，14， 49，{54} 五、算法设计 .假设二叉树T采用如下定义的存储结构： typedef struct node { DataType data; struct node *lchild,*rchild; }BinTree;