1、全国自考（数据结构）模拟试卷 6 及答案与解析一、单项选择题1 在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 ( )（A）先序遍历（B）中序遍历（C）后序遍历（D）按层次遍历2 已知一个向量的第一个元素的存储地址是 loO，每个元素的长度为 2，则第 6 个元素的地址是 ( )（A）120（B） 112（C） 110（D）1143 在单链表中，删除 p 所指结点的直接后继的操作是 ( )（A）pnext=pnextnext;（B） p=pnext;p next=pnextnext;（C） pnext=p next;（D）p=pnext next;4 深度为 6(根的层次为 1)的
2、二叉树至多有( ) 个结点。（A）31（B） 32（C） 63（D）645 设二叉树有 n 个结点，则其深度为 ( )（A）n-1（B） n（C）（D）不确定6 在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 ( )（A）先根遍历（B）中根遍历（C）后根遍历（D）按层次遍历7 一个栈的入栈序列为 a1,a2,a3,a4,a5，则此栈不可能的输出序列是 ( )（A）a5,a4,a3,a2,a1（B） a4,a5,a3,a2,a1（C） a4,a3,a5,a1,a2（D）a1,a2,a3,a4,a58 设 rear 是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为(
3、 )（A）s=rear;（B） rear=rearnext; rear=rearnext; free(rear); free(s);（C） rear=rearnext next;（D）s=rearnext next; free(rear); rearnextnext=s next; free(s);9 以下有关数据结构的叙述，正确的是 ( )（A）线性表的线性存储结构优于链式存储结构（B）二叉树的第 i 层上有 2i-1 个结点，深度为 K 的二叉树上有 2k-1 个结点（C）二维数组是其数据元素为线性表的线性表（D）栈的操作方式是先进先出10 已知一个单链表中有 3000 个结点，每个结点存
4、放一个整数，( )可用于解决这3000 个整数的排序问题且不需要对算法作大的变动。（A）直接插入排序方法（B）简单选择排序方法（C）快速排序方法（D）堆排序方法11 二维数组 Mi,j的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标i 的范围从 0 到 4，列下标 j 的范围从 0 到 5。M 按行存储时元素 M3,5的起始地址与 M 按列存储时元素( )的起始地址相同。（A）M2,4（B） M3,4（C） M3,5（D）M4,412 在一棵二叉树中，第 k 层上最多有( )个结点。（A）2k（B） 2k-1（C） 2k（D）2 k-113 一棵二叉树如图所示，其中序遍历的序列为
5、 ( )（A）ABDGCEFH（B） DGBAECHF（C） GDBEHFCA（D）ABCDEFGH14 设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。（A）线性表的顺序存储结构（B）栈（C）队列（D）线性表的链式存储结构15 设有一顺序栈 S，元素 s1，s 2，s 3，s 4，s 5，s 6 依次进栈，如果 6 个元素出栈的顺序是 s2，s 3，s 4，s 5，s 6，s 1，则栈的容量至少应该是 ( )（A）2（B） 3（C） 5（D）6二、填空题16 在直接插入和直接选择排序中，如果初始数据基本正序，则选用_，若初始数据基本反序，则选用_。17 设一个链栈的
6、栈顶指针为 ls，栈中结点两个字段分别为 info 和 next，其中 next是指示后继结点的指针，栈空的条件是_。如果栈不空，则退栈操作为p：=ls；_ ；dispose(p)。18 在分块查找法中，首先查找_，然后再查找相应的_。19 对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于A00的地址为_。20 在一个按行优先顺序存储的二维数组(MN) 中，假设数组的基地址是 P，并且数组的每一个元素所占的存储空间为 d 个字节，则 aij 的地址计算公式为_。21 对角矩阵中，除了_的元素之外，其余的元素都是零。则对于一个 k 对角线矩阵(k 为奇数)A 是满足下面的条
7、件的矩阵；如果_，则元素 aij=0。22 _中结点的最大度数允许大于 2，而_中结点的最大度数不允许大于2。23 计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是_。24 在单链表中，除了首元结点外，任一结点的存储位置是由_指示。25 大多数排序算法都有两个基本操作，它们是_和_。三、解答题26 对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。27 假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。28 假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。29 已知一棵二叉
8、树按照顺序结构存储，其存储结构如下： 则请回答如下问题： (1)请画出此二叉树的树形结构。 (2)请写出此二叉树的前序遍历、中序遍历和后序遍历序列。 (3)此二叉树的高度是多少? (4)结点 F 的双亲、孩子，以及祖先分别是什么? (5) 此树中，度数为 1 的结点共有几个? 分别是哪几个? (6)结点 C 有左孩子吗? 如果有左孩子，则 C 的左孩子的编号应该是什么?四、算法阅读题30 以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lklist(1klist head,int i) p=head;j=0; while(_) p=pnext;j+;
9、 if(i=j)return(p); else return(NULL); 31 以下算法实现若开散列表 HP 中存在键值为 K 的结点，则将其删除。请分析程序，并在_上填充合适的语句。 void delete_openhash(keytype K,openhash HP) i=H(K); if(HPi=NULL)return; /*空表则退出*/ p=HVi; if(pkey=K)_=pnext;free(p);return;) /*表首结点为待删除结点时的删除 */ while(pnext!=NULL) /*其他情况下的删除 */ q=p;p=pnext; if(p key=K)_=pne
10、xt;delete(p);return;) 32 以下运算实现在循环队上的出队列，请在_处用适当的语句予以填充。 int OutCycQueue(CycqueueTp*sq,DataType*x) if(sqfront=_)error(“队空“);return(0);) else_; _; return(1); 33 以下为求单链表表长的运算，分析算法，请在_处填上正确的语句。 int length_lklist(lklist head) /*求表的长度。 */ _; j=0; while(pnext!=NULL) _; j+; return(j); /*回传表长*/五、算法设计题34 从键盘
11、上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。全国自考（数据结构）模拟试卷 6 答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 C3 【正确答案】 A4 【正确答案】 B5 【正确答案】 D6 【正确答案】 D7 【正确答案】 C8 【正确答案】 D9 【正确答案】 C10 【正确答案】 D11 【正确答案】 B12 【正确答案】 D13 【正确答案】 B14 【正确答案】 B15 【正确答案】 B二、填空题16 【正确答案】 直接插入排序 直接选择排序17 【正确答案】 ls=null 这是
12、指链栈没有设置头结点的情况，一般情况下也不必设置 ls： =ls.next；这一操作让头指针指示下一个结点18 【正确答案】 索引表块19 【正确答案】 ij+i 全元素位置20 【正确答案】 LOC(a ij)=P+iN+jd21 【正确答案】 主对角线和主对角线相临两侧的若干条对角线上 ik 或 jk22 【正确答案】 树 二叉树23 【正确答案】 固定长度 设置长度指针24 【正确答案】 其直接前趋结点的链域的值25 【正确答案】 比较两个关键字的大小 改变指向记录的指针或者移动记录本身三、解答题26 【正确答案】 从三元组表还原稀疏矩阵时，首先根据表的第 1 行得出稀疏矩阵的行数和列数
13、，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2) 所示。 27 【正确答案】 稀疏矩阵的三元组指的是矩阵中非零元素的行号、列号和其对应的元素，而三元组表就是将其结点是三元组的线性表按照顺序结构进行存储，其表的结构为：(其中 i 代表行号，j 代表列号，v 指的是相应的元素值) 28 【正确答案】 假设判定树的内部结点的总数为 n=2h-1-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第 k 层上的结点的个数为 2h-1，查找它们所需要比较的次数是 k。则在
14、等概率下，二分查找成功时的平均查找长度为：，如果 n 很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于 2 的结点只可能在最下面的两层上29 【正确答案】 (1)此二叉树如图所示： (2)前序遍历序列为：ABDEFGMCHJ 中序遍历序列为： EDGFMBACHJ 后序遍历序列为：EGMFDBAJHC (3)此树的高度是 5。 (4)结点 F 的双亲是 D，孩子是 G，M(其中 G是其左孩子，M 是其右孩子)，祖先是 D，B，
15、A。 (5) 此树中度数为 1 的结点共有3 个，分别为 B，C ，H。 (6)结点 C 没有左孩子，如果它有左孩子，则左孩子的编号为 6(23=6)四、算法阅读题30 【正确答案】 (pnext!=NULL) char str80,ch; fILE*fp; fp=fopen(“text“,“w“); for(flag=1:flag;)/*输入字符串*/ printf (“n 输入字符串：n“) gets(str); fprintf(fp,“%t“,str); printf(“eoutinnue? Y/N“); if(ch=getchar()=“n“)!(ch=n) flag=0; getehar(); fseek(fp,0,0); while(fscanf(fp,“%s“,str)!=EOF) for(i=.0;stri=e;i=) if(stri=a) stri=Z /*小写字母进行转换*/ stri=stri-32; printf(“n%n“,str); fclose(fp); /*main*/
