1、全国自考（数据结构）模拟试卷 2 及答案与解析一、单项选择题1 循环链表的主要优点是( )（A）不再需要头指针了（B）已知某个结点的位置后，能够容易找到它的直接前趋（C）在进行插入、删除运算时，能更好地保证链表不断开（D）从表中任一结点出发都能扫描到整个链表2 磁带适合存储的文件类型是( )（A）索引文件（B）顺序文件（C）散列文件（D）多关键字文件3 下面的查找方式中，可以对无序表进行查找的是( )（A）顺序查找（B）二分查找（C）二叉排序树（D）B-树上的查找4 ( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（A）归并排序（B）插入排序（C）快速排序（D
2、）选择排序5 在一个具有 N 个顶点的无向完全图中，包含的边的总数是 ( )（A）N(N-1)/2（B） N(N-1)（C） N(N+1)（D）N(N+1)/26 在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。（A）snext=pnext;pnext=s;（B） qnext=s;snext=p;（C） pnext=s next;s next=p;（D）pnext=s;s next=q;7 如果一个队列的入队顺序是 1,2,3,4,5，则此队列的出队顺序是( )（A）5,4,3,2,1（B） 4,5,1,2,3（C） 1,2,3
3、,4,5（D）不确定8 静态查找表与动态查找表二者的根本差别在于( )（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储实现不一样9 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )（A）每个结点所代表的数据元素都一样（B）每个结点所代表的数据元素包含的数据项的个数要相等（C）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致（D）结点所代表的数据元素有同一特点10 非空的循环单链表 head 的尾结点(由指针 p 所指)满足( )（A）pnext=NULL（B） p
4、=NULL（C） pnext=head（D）p=head11 考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )（A）直接插入排序和快速排序（B）快速排序和归并排序（C）直接选择排序和归并排序（D）直接插入排序和归并排序12 下面关于线性表的叙述错误的是( )（A）线性表采用顺序存储，必须占用一片连续的存储单元（B）线性表采用顺序存储，便于进行插入和删除操作（C）线性表采用链接存储，不必占用一片连续的存储单元（D）线性袁采用链接存储，不便于插入和删除操作13 假定一棵二叉树的结点为 18 个，则此二叉树的最大高度为( )，最小高度为( )（A）4（B） 5（
5、C） 6（D）1814 当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )（A）n 2（B） nlonan（C） log2n（D）n-115 栈一般情况下常采用以下两种存储方式( )（A）顺序结构和散列结构（B）散列结构和链式结构（C）线性结构和非线性结构（D）顺序存储结构和链式结构二、填空题16 _的有向图，其全部顶点有可能排成一个拓扑序列。17 朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是_(假设模式串的长度是 m，目标串的长度是 n)。18 任何连通图的连通分量只有一个，即_。19 设有一个已按各元素的值排好序的线性表，长度为 125
6、，对给定的 k 值，用二分法查找与 k 相等的元素，若查找成功，则至少需要比较_次，至多需比较_次。20 在非空队列中，头指针始终指向_，而尾指针始终指向_。21 数组的长度是_，线性表的长度是_。22 如果一个图中有 n 条边，则此图的生成树含有_条边，所以生成树是图的边数_的连通图。23 设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是 1000，则 A15,10的存储地址是_ 。24 顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即_和_。25 在线性表的顺序存储中
7、，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。三、解答题25 设有多项式 A(x)=7+3x+9x 8+5x17 B(x)=8x+22x7 一 9x826 用单链表给出 A(x)的存储表示。27 用单链表给出 B(x)的存储表示。28 以上述两个单链表为基础，通过插入和删除等运算得出 A(x)+B(x)的存储表示，使其存储空间覆盖 A(x)和 B(x)的存储空间。29 假设一个循环队列的容量为 50，对其进行人队和出队操作，则经过一段时间之后，有： (1)front=35，rear=12； (2)front=12，rear=35。 其中 front
8、 和 rear 分别是队头和队尾指针。 求：循环队列中元素的个数?30 已知散列函数为 H(K)=K mod 12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。31 请画出二叉树的五种基本形态。四、算法阅读题32 以下运算实现在循环队上取队头，请在_处用适当的语句予以填充。 int GetHead(CycqueueTp sq,DataType*x) if(sq.rear=_return(0); else*x=sq.data_; return(1); 33 以下是图的广度优先搜索算法，请在_
9、处填充适当的语句。 Bfs(GraphTp g,int v) QueptrTp Q; ArcNodeTp*P; InitQueue( printf(“%“”,v); visitedv=1; _ while(!EmptyQueue(Q) _; p=g.adjlistv.firstarc; while(p! =NULL) if(! visitedpadjvex) printf(“%“”,padjvex); visitedpadjvex=1); EnQueue( _; 34 以下为单链表的定位运算，分析算法，请在_处填上正确的语句。 int locate_iklist(1klist head,dat
10、atype x) /*求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0*/ p=head;j=O; while(_)p=pnext;j+; if(pdata=x)return(j); elsereturn(0); 35 下列算法用于判断带头结点的循环双链表 A 是否对称相等，请在算法中的一填上正确的语句。 int dlink_symmetry(dlklist s) j=true; p=snext; q=sprior; while(p!=q) (_); else j=false; return(j); 五、算法设计题36 若输入 12000 个不同的整数，其值介于 0
11、 和 19999 之间，采用散列表存储这些数，散列函数为 h(k)=k/2，请设计实现的算法。全国自考（数据结构）模拟试卷 2 答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 B3 【正确答案】 A4 【正确答案】 C5 【正确答案】 A6 【正确答案】 B7 【正确答案】 C8 【正确答案】 B9 【正确答案】 C10 【正确答案】 C11 【正确答案】 C12 【正确答案】 A13 【正确答案】 B14 【正确答案】 D15 【正确答案】 D二、填空题16 【正确答案】 存在入度为 O 的结点且没有回路17 【正确答案】 0(m+n)18 【正确答案】 其自身19 【正确答案
12、】 1 720 【正确答案】 队头元素 队尾元素21 【正确答案】 固定的 可变的22 【正确答案】 n-1 最少23 【正确答案】 170024 【正确答案】 静态存储分配的顺序串 动态存储分配的顺序串25 【正确答案】 相邻位置 链接指针三、解答题26 【正确答案】 每一结点由三个域组成27 【正确答案】 类似地，B(x)可表示为28 【正确答案】 在实现 A(x)+B(x)时，可以 A(x)的单链表为基础，逐项考虑 B(x)。若 B(x)中某项的指数与 A(x)某项指数一致，则将两个相应的系数相加，若结果为0，则从 A(x)单链表中删去此项的结点；若结果不为 0，则修改 A(x)单链表中
13、该项的系数域，使之表示同类项合并的结果。若 B(x)中某项的系数在 A(x)单链表中未出现，则将该项结点插入 A(x)的单链表中。这样就得到下列重复使用 A(x)和 B(x)存储空间的 A(x)+B(x)的存储袁示。29 【正确答案】 如果一个循环队列的总容量为 N，则当 rear-front 时，循环队列中的元素的个数为 rear-front，当 earfront 时，循环队列中的元素的个数为N+(rear-front)。所以此题中：(1) 循环队列中元素的个数为 35-12=23；(2)循环队列中元素的个数为 50+(12-35)=27。30 【正确答案】 查找成功的平均查找长度为：(4*
14、2+8)，12=4/331 【正确答案】 二叉树有五种不同的基本形态： A ：空二又树 B ：只有一个根结点的二叉树 C：右子树为空的二叉树 D：左子树为空的二叉树 E：左、右子树都非空的二叉树 四、算法阅读题32 【正确答案】 sq.front(sq.front+1)% maxsize33 【正确答案】 EnQueue( seqlist R; int i,j,k,n; for(i=0;i 12000;i+) Hi.data=-1; Hi.next=-1；/*初始化*/ n=0; for(k=0;k12000;k+) scanf(i); j=i/2; if(Hj.data!=-1) Hj.next=n; An=i; n+; else Hj.data=i; /*hash*/
