数据结构自考题-7

1、数据结构自考题 -7( 总分： 115.00 ，做题时间： 90 分钟 )一、单项选择题 ( 总题数： 15，分数： 30.00)1. 已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法是( )A. 将该元素所在的存储单元清空B. 将该元素用一个特殊的元素替代C. 将与该元素有相同 Hash地址的后继元素顺次前移一个位置D. 用与该无素有相同 Hash地址的最后插入表中的元素替代(分数： 2.00 )A.B. VC.D.解析：2. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )A. 不一定相同B 都相同C 都不相同D 互为逆序分数

2、： 2.00 )A.B. VC.D.解析：3. 对于一棵具有三个结点的二叉树，共有 ( ) 种不同的树的形态。A. 4 B. 5 C. 6 D. 7分数： 2.00 )A.B. VC.D.解析：4. 栈一般情况下常采用以下两种存储方式 ( )A. 顺序结构和散列结构B 散列结构和链式结构C.线性结构和非线性结构D 顺序存储结构和链式结构(分数： 2.00 )A.B.C.D. V解析：5. 考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )A. 直接插入排序和快速排序B 快速排序和归并排序C.直接选择排序和归并排序D 直接插入排序和归并排序(分数： 2.00

3、)A.B.C. VD.解析：6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( )A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等(分数： 2.00 )A.B. VC.D.解析：7. 下列说法中正确的是 ( )A. 任何一棵二叉树中至少有一个结点的度为2B. 任何一棵二叉树中的每个结点的度为2C. 任何一棵二叉树中的度肯定等于2D. 任何一棵二叉树中的度可以小于2（分数： 2.00 ）A.B.C.D. V解析：8. 若进栈序列为 1,2,3,4,5,6 ，且进栈

4、和出栈可以穿插进行，则可能出现的出栈序列为 （ ）A. 3,2,6,1,4,5 B . 3,4,2,1,6,5 C . 1,2,5,3,4,6 D . 5,6,4,2,3,1（分数： 2.00 ）A.B. VC.D.解析：9. 设串 s1="Data Structures 、with Java" ， s2="it" ，则子串定位函数 index（s1 ， s2） 的值为 （ ）A. 15 B . 16 C . 17 D . 18（分数： 2.00 ）A.B.B. VD.解析：10. 在一个具有N个顶点的无向完全图中，包含的边的总数是（）AN（N-1）/2

5、 B N（N-1） C N（N+1） DN（N+1）/2（分数： 2.00 ）A. VB.C.D.解析：11. 二维数组 Mi,j 的元素是 4个字符（每个字符占一个存储单元 ）组成的串， 行下标 i 的范围从 0到4，列 下标j的范围从0到5。M按行存储时元素 M3,5的起始地址与 M按列存储时元素（）的起始地址相同。AM2,4 B M3,4 C M3,5 D M4,4（分数： 2.00 ）A.B. VC.D.解析：12. 按值可否分解，数据类型通常可分为两类，它们是 （ ）A.静态类型和动态类型 B 原子类型和表类型C.原子类型和结构类型 D 数组类型和指针类型（分数： 2.00 ）A.B

6、.C. VD.解析： 解析 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其 值可分解为若干个成分。13. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数（）对应的判定树的高度（假设树高h>2）。A.大于B .小于C 等于D .无法确定分数： 2.00 ）A.B. VC.D.解析：14. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ ）A.层次遍历算法 B 前序遍历算法 C 中序遍历算法D 后序遍历算法分数： 2.00 )A.B.C. VD.解析：15.指针p、q和r依次指向某循环链表中三个相邻的结点，交

7、换结点*q和结点*r在表中次序的程序段是（）A.p> next=r; q> next=r > next; r > next=q;B.p> next=r; r> next=q; q> next=r> next;C.r> next=q; q> next=r > next; p > next=r;D.r> next=q; p> next=r; q> next=r> next;（分数： 2.00 ）A. VB.C.D.解析：二、填空题 （总题数： 10，分数： 20.00）。按外设的观点所确定的基本存储单元

8、称16. 就文件而言， 按用户的观点所确定的基本存储单元称为 为。（分数： 2.00 ）填空项 1: （正确答案：逻辑记录 物理记录）解析：17. 在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是1（分数： 2.00 ）填空项 1: （正确答案：选择排序）解析：18. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1（分数： 2.00 ）填空项 1: （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：19. 设s="l AM A ATHLETE" , t="GOOD",则执行下列串操作序列之后

9、得到的suhl为。substr（sub1,s,5,2）;substr（sub2,s,6,8）;strcpy（t1,t）;strcat,（t1,sub2）;strcat（sub1,t1）;（分数:2.00 ）填空项1: （正确答案："A GOOD ATHLETE）解析：20. 从一个顺序存储的循环队列中删除一个元素时，应该1。（分数:2.00）填空项1： （正确答案：先移动队首指针，后取岀元素）解析：21. 设二维数组A10 20,5 10按行优先存储，每个元素占4个存储单元，A10,5的存储地址是1000，则A15,10的存储地址是 1。（分数：2.00 ）填空项1: （正确答案：1

10、700）解析：22. 从树的根结点到树中的其余结点之间的路径1惟一的（分数：2.00 ）填空项1： （正确答案：是）解析：23. 如图所示的有向图中含有 个强连通分量（分数：2.00 ）填空项1： （正确答案：2）解析：24. 假设以列优先顺序存储二维数组A58，其中元素A00的存储地址为LOC®），且每个元素占4个存储单元，则数组元素Aij的存储地址为1。（分数：2.00 ）填空项 1: （正确答案：LOC（st0）+4（5j+i）解析：25. 存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用 和进行查找（分数：2.00 ）填空项1: （正确答案：二分查找法分块查找）解析

11、：三、解答题（总题数：3,分数：20.00）26. 某广义表的表头和表尾均为（a,（b,c），画出该广义表的图形表示（分数：5.00 ）正确答案：（解析: 已知有向图G的定义如下:G=(V,E)V=a,b,c,d,eE=< a,b >,< a,c >,< b,c >,< b,d >,< c,d >,< e,c >,< e,d >)(1) 画出G的图形；(2) 写岀G的全部拓扑序列。(分数：10.00 )解析: 正确答案：（a,b,e,c,da,e,b,c,de,a,b,c,d）解析：，如果我们采用直接选择排序方

12、法对此序27. 已知有一关键字序列为97,86,53,108,72,34,215,146,11,68列进行排序（按照升序排列），请给岀每一趟的排序结果。（分数：5.00 ）正确答案：（直接选择排序的过程为：从第i趟开始时，当前的有序区和无序区分别为R1i和R1n（1 < -1<n-1），则在该趟排序是从当前无序区中选出关键字最小的记录RK，将它与无序区中的第1个记录Ri交换，使R1i和Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区 增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：初始：97,86,53,108,72,34,215,232,11,6

13、8第 1 趟：1186,53,108,72,34,215,232,97,68第 2 趟：11,3453,108,72,86,215,232,97,68第 3 趟：11,34,531108,72,86,215,232,97,68第 4 趟：11,34,53,6872,86,215,232,97,108第 5 趟：11,34,53,68,7286,215,232,97,108第 6 趟：11,34,53,68,72,86215,232,97,108第 7 趟：11,34,53,68,72,86,97232,215,108第 8 趟：11,34,53,68,72,86,97,108215,232第

14、9 趟：11,34,53,68,72,86,97,108,215,232）解析：四、算法阅读题（总题数：3,分数：25.00）28. 求下面算法中变量count的值：（假设n为2的乘幂，并且n >2）int Timeint ncount=0;x=2;while(x < n/2) x*=2;count+;return(count)（分数：5.00 ） 正确答案：(count=log 2n)解析：29. 简述一下算法的功能：status A (1inkedlist L)/L是无表头结点的单链表if (L&&L > next) Q=L;L=L> next;P=

15、L;while(P > next)P=P > next; P> next=Q;Q > next=NULL;return ok;)/A（分数：5.00 ）正确答案：（本程序实现的功能就是：如果L的长度不小于2,则将首元结点删去并插入到表尾。）解析：二叉排序树的存储结构定义为以下类型：typedef int KeyType;typedef struct nodeKeyType key; /*关键字项 */InfoType otherinfo; /*其它数据项 */struet node*lchild,*rchild; /*左、右孩子指针 */BSTNode,*BSTree;

16、阅读算法f33，并回答问题：(1)对如图所示的二叉排序树T,写出f33(T,8)返回的指针所指结点的关键字;在哪些情况下算法f33返回空指针？简述算法f33的功能。BSTNode*f33(BSTree T,KeyType x)BSTNode*P; if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;if(T > key > x)return T;return f33(T> rchild,x);(分数：15.00 )正确答案： （10）解析： 正确答案：仃是空树或T中所有结点的关键字均不大于给定值 X

17、时，返回空指针。） 解析：正确答案：（如果二叉排序树T中存在含有关键字大于给定值X的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。 ）解析：五、算法设计题 （ 总题数： 1，分数： 20.00） 假设以带双亲指针的二叉链表作为 - 二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType;typedef struct nodeDataType data;struct node*lchild,*rchild; /左右孩子指针struct node*parent; / 指向双亲的指针BinTNode;typedef BinTNode*BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。（分数： 20.00 ）（1）. 就后继的不同情况，简要叙述实现求后继操作的方法；（分数：10.00 ） 正确答案： （ 分两种情况讨论 当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结 点为止，则该结点为 *pX 在中序序列中的后继； 当 *px 的右子树为空时，则沿 *px 的双亲指针链向上查找，直至找到其左子树中包含 *px 的最年轻祖先， 则该祖先结点为 *px 在中序序列中的后继。 ）解析：（2）. 编写算法求 px 所指结点的中序序列