2006年上半年全国自考数据结构真题及答案.doc

更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你.2006年上半年全国自考数据结构真题一、单项选择题（每小题2分，共30分）在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者，该题无分。1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答案：C2.下面程序段的时间复杂度为s=0;for(i=1;i=n;i+)for(j=0;j=n;j+)s=s+bij;（）A.AB.BC.CD.D答案：C3.用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（）A.当前结点所在地址域B.指针域C.空指针域D.空闲域答案：B4.在队列中存取数据的原则是（）A.后进先出B.先进先出C.后进后出D.随意进出答案：B5.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为（）A.AB.BC.CD.D答案：A6.广义表A=(x,(a,b),(x,(a,b),y),则运算head（head(tail(A)为（）A.xB.a,b)C.(x,(a,b)D.A答案：A7.A.AB.BC.CD.D答案：A8.串的长度是（）A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数n(n0)D.串中所含字符的个数n(n0)答案：D9.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（）A.AB.BC.CD.D答案：D10.在一个具有n个结点的无向完全图中，包含有（）条边。A.AB.BC.CD.D答案：A11.设有一个栈，元素的进栈次序为A，B，C，D，E，（）是不可能的出栈序列。A.A，B，C，D，EB.B，C，D，E，AC.E，A，B，C，DD.E，D，C，B，A答案：C12.在所有的排序方法中，关键字的比较次数与记录的初始排序无关的是（）A.Shell排序B.冒泡排序C.直接插入排序D.直接选择排序答案：D13.具有2000个结点的二叉树，其高度至少为（）A.9B.10C.11D.12答案：C14.下面的序列中，（）是堆。A.1，2，8，4，3，9，10，5B.1，5，10，6，7，8，9，2C.9，8，7，6，4，8，2，1D.9，8，7，6，5，4，3，7答案：A15.数据结构是研究数据的（）及其之间的相互关系。A.存储结构，理想结构B.理想结构，抽象结构C.存储结构，逻辑结构D.抽象结构，逻辑结构答案：C二、填空题（每小题2分，共20分）1.前序序列和_可以唯一的确定一棵二叉树。答案：中序序列2.顺序表相对于链表的优点有_和_。答案：节省存储空间 随机存取3.设有一个稀疏图G，则G采用_存储较节省空间。答案：邻接表4.散列法存储的基本思想是由_决定数据的存储地址。答案：关键字的值5.森林的后序遍历序列正是相应二叉树的_遍历序列，森林的先序遍历序列正是相应二叉树的_遍历序列。答案：中序 先序6.在插入和选择排序中，若初始数据基本正序，则选择_；若初始数据基本反序，则选用_。答案：插入排序 选择排序7.对于二叉树来说第i层至多有_个结点。答案：8.在循环链表中，可根据在一结点的地址遍历整个链表，而单链表中需知道_才能遍历整个链表。答案：头指针9.设n阶方阵是一个上三角矩阵，则需存储的元素个数为_。答案：n(n+1)/210.多关键字文件是指_。答案：有一个主关键字多个次关键字三、简答题(每小题5分，共15分)1.简述线性表的顺序和链式存储结构及各自的长处。答案：答:顺序表用结点物理位置的相邻性来反映结点间的逻辑关系,其优点是:节省存储空间，随机存取，当表长变化较小，主要操作是进行查找时，宜采用顺序表。（3分）链表用附加的指针来反映结点的逻辑关系，当表长变化较大，主要操作是进行插入和删除时，宜采用链表。（5分）2.循环队列的优点是什么？如何判别它的空和满（用浪费一个元素的空间的方法说明）？答案：答：循环队列的优点是解决了假上溢问题。（2分）为解决队空、队满的判断问题，使队头指针、队尾指针中有一个指向实在元素，有一个指向实在元素边上的空闲元素。虽然这种方法浪费了一个元素的空间，但使队空、队满的判断问题分离。此时队空标志是Qfront=Qrear,队满标志是Qfront=（Qrear+1）%QueueSize。（5分）3.选择排序算法是否稳定？为什么？答案：答：选择排序不稳定。（2分）由于选择排序的原则是从剩余的记录中找最小（或最大）者并与第i个记录交换，一旦交换到某个位置以后再也不动了，这种算法就不能保证具有相同排序码的记录原来所具有的相对次序，即原来排在前面的经过排序后有可能排在某个具有相同码的记录的后面。例如排序码43，89，21，43，28，15，经过5遍排序后次序为15，21，28，43，43，89。排序前第一个位置上的排序码43现在位于第5个位置。（5分）四、求解下列问题（每小题5分，共15分）1.有一电文中共使用5个字符A，B，C，D，E，他们出现的频率依次为4，7，5，2，9。试画出对应的哈夫曼树，求出WPL，为每个字符设计哈夫曼编码。答案：解：哈夫曼树如图由哈夫曼树得WPL=(2+4)3+(5+7+9)2=60(3分)哈夫曼编码如下：A：001B：10C：01D：000E：11(5分)2.对下图所示的连通图，请用普里姆（Prim）算法构造其最小生成树。答案：3.对于给定关键字序列503,087,512,061,908,170,897,275,653,462，写出在快速排序运行下各趟结果。答案：解：503，087，512，061，908，170，897，275，653，462462,087,275,061,170,503,897,908,653,512(2分)170,087,275,061，462,503,512,653,897,908(3分)061,087，170,275,462,503,512,653,897,908(4分)061,087,170,275,462,503,512,653,897,908(5分)五、读程序填空题（8分）1.该算法实现的内容是：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。结点类型定义如下：typedef struct node Date Type data;Struct node *next; listNode;typedef listNode *linklist;LinkList CreatListF(void)char ch;LinkList head;ListNode*s;head=NULL;ch=getchar();(1)while()(2);sdata=ch;(3)head=s;更多优质自考资料尽在百度贴吧自考乐园俱乐部（/club/5346389）欢迎加入.欢迎交流.止不住的惊喜等着你.(4)return head;答案：（1）ch!=n(2分)（2）s=(ListNode*)malloc(sizeof(ListNode)(4分)（3）snext=head;(6分)（4）ch=getchar()；(8分)六、算法设计题（12分）1.回文是指正读和反读均相同的字符序列，如“ABBA”。试写一个算法判定字符是否为回文。算法的返回值为1代表是回文，为0代表不是回文。答案：算法为：#define stacksize 100/*字符串最大长度，可更改*/typedef char DataType;typedef structDataType datastacksize;int top;seqstack;(4分)int example(char a)seqstack*s;int n,i,mid;intstack(s);n=strlen(a);(6分)for(