《数据结构自考题-7》由会员分享，可在线阅读，更多相关《数据结构自考题-7（9页珍藏版）》请在金锄头文库上搜索。
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 B N（N-1） C N（N+1） DN（N+
5、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.C. VD.解析： 解析 按“值”是否可分解，
6、可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其 值可分解为若干个成分。13. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数（）对应的判定树的高度（假设树高h2）。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依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（）A.p ne
7、xt=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）。按外设的观点所确定的基本存储单元称16. 就文件而言， 按用户的观点所确定的基本存储单元称为 为。（分数： 2.00 ）填空项 1: （正确答案：逻辑记录 物理记录）解析：17. 在一般情况下用直接插入排序、选择排序和冒泡排
8、序的过程中，所需记录交换次数最少的是1（分数： 2.00 ）填空项 1: （正确答案：选择排序）解析：18. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1（分数： 2.00 ）填空项 1: （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：19. 设s=l AM A ATHLETE , t=GOOD,则执行下列串操作序列之后得到的suhl为。substr（sub1,s,5,2）;substr（sub2,s,6,8）;strcpy（t1,t）;strcat,（t1,sub2）;strcat（sub1,t1）;（分数:2.00 ）填空项1: （正确答案：A GOO
9、D ATHLETE）解析：20. 从一个顺序存储的循环队列中删除一个元素时，应该1。（分数:2.00）填空项1： （正确答案：先移动队首指针，后取岀元素）解析：21. 设二维数组A10 20,5 10按行优先存储，每个元素占4个存储单元，A10,5的存储地址是1000，则A15,10的存储地址是 1。（分数：2.00 ）填空项1: （正确答案：1700）解析：22. 从树的根结点到树中的其余结点之间的路径1惟一的（分数：2.00 ）填空项1： （正确答案：是）解析：23. 如图所示的有向图中含有 个强连通分量（分数：2.00 ）填空项1： （正确答案：2）解析：24. 假设以列优先顺序存储二维
10、数组A58，其中元素A00的存储地址为LOC），且每个元素占4个存储单元，则数组元素Aij的存储地址为1。（分数：2.00 ）填空项 1: （正确答案：LOC（st0）+4（5j+i）解析：25. 存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用 和进行查找（分数：2.00 ）填空项1: （正确答案：二分查找法分块查找）解析：三、解答题（总题数：3,分数：20.00）26. 某广义表的表头和表尾均为（a,（b,c），画出该广义表的图形表示（分数：5.00 ）正确答案：（解析: 已知有向图G的定义如下:G=(V,E)V=a,b,c,d,eE=,)(1) 画出G的图形；(2) 写岀G的全
11、部拓扑序列。(分数：10.00 )解析: 正确答案：（a,b,e,c,da,e,b,c,de,a,b,c,d）解析：，如果我们采用直接选择排序方法对此序27. 已知有一关键字序列为97,86,53,108,72,34,215,146,11,68列进行排序（按照升序排列），请给岀每一趟的排序结果。（分数：5.00 ）正确答案：（直接选择排序的过程为：从第i趟开始时，当前的有序区和无序区分别为R1i和R1n（1 -12）int Timeint ncount=0;x=2;while(x next) Q=L;L=L next;P=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
