1、全国2012年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。1一个算法的时间耗费的数量级称为该算法的 A
2、效率 B难度 C可实现性 D时间复杂度2顺序表便于 A插入结点 B删除结点 C按值查找结点 D按序号查找结点3设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 Ap-next-next=head Bp-next=head Cp-next-next=NULL Dp-next=NULL 4设以数组A0.m-1存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A(rear-front+m)m Brear-front+1 C(front-rear+m)m D(rear-front)m 5下列关于顺序栈的叙述中，正确的是 A入栈操作需
3、要判断栈满，出栈操作需要判断栈空 B入栈操作不需要判断栈满，出栈操作需要判断栈空 C入栈操作需要判断栈满，出栈操作不需要判断栈空 D入栈操作不需要判断栈满，出栈操作不需要判断栈空6A是一个1010的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为 A25 B26 C33 D34 7树的后序遍历等价于该树对应二叉树的 A层次遍历 B前序遍历 C中序遍历 D后序遍历8使用二叉线索树的目的是便于 A二叉树中结点的插入与删除 B在二叉树中查找双亲 C确定二叉树的高度 D查找一个结点的前趋和后继9设无向图的顶点个数为n，则该图边的数目最
4、多为 An-l Bn(n-1)2 Cn(n+1)2 Dn210可进行拓扑排序的图只能是 A有向图 B无向图 C有向无环图 D无向连通图11下列排序方法中稳定的是 A直接插入排序 B直接选择排序 C堆排序 D快速排序12下列序列不为堆的是 A75,45,65,30,15,25 B75,65,45,30,25,15 C75,65,30,l5,25,45 D75,45,65,25,30,1513对线性表进行二分查找时，要求线性表必须是 A顺序存储 B链式存储 C顺序存储且按关键字有序 D链式存储且按关键字有序14分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 的序列是 A(
5、4,1,2,3,5) B(4,2,3,l,5) C(4,5,2,1,3) D(4,2,1,5,3)15下列关于m阶B树的叙述中，错误的是 A每个结点至多有m个关键字 B每个结点至多有m棵子树 C插入关键字时，通过结点分裂使树高增加 D删除关键字时通过结点合并使树高降低非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共10小题，每小题2分，共20分)16数据元素之间的逻辑关系称为数据的_结构。17在线性表中，表的长度定义为_。18用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到 1、3、4、2的出栈顺序，相应的S和
6、X的操作序列为_。19在二叉树中，带权路径长度最短的树称为_。20已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是_。21一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符d的哈夫曼编码的长度为_。22在一个具有n个顶点的无向图中，要连通全部顶点至少需要_条边。23直接选择排序算法的时间复杂度是_。24对于长度为81的表，若采用分块查找，每块的最佳长度为_。25用二叉链表保存有n个结点的二叉树，则结点中有_个空指针域。三、解答题(本大题共4小题，每小题5分，共20分)26假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一
7、个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0；写出依次执行 下列操作后头、尾指针的当前值。 a,b,c,d,e,f入队，a,b,c,d出队； (1) Q.front=_；Q.rear=_。 g,h,i,j,k,l入队，e,f,g,h出队； (2) Q.front=_；Q.rear=_。 M,n,o,P入队， i,j,k,l,m出队； (3) Q.front=_；Q.rear=_。27已知一个无向图如题27图所示，以为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。28用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问
8、： (1)一共需要几趟归并可完成排序。 (2)写出第一趟归并后数据的排列次序。29一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key11将记录 散列到散列表HT0.12中去，用线性探测法解决冲突。 (1)画出存入所有记录后的散列表。 (2)求在等概率情况下，查找成功的平均查找长度。四、算法阅读题(本大题共4小题，每小题5分，共20分)30顺序表类型定义如下： # define ListSize 100 typedef struct int dataListSize； int length； SeqList； 阅读下列算法，并回答问题： voi
9、d f30(SeqList *L) int i,j； i=0； while(ilength) if (L-datai2!=0) for(j=i+1; jlength; j+ L-dataj-1=L-dataj; L-length-;else i+（1）若L-data 中的数据为（22,4,63,0,15,29,34,42,3）,则执行上述算法后L-data中的数据以及L-length的值各是什么？（2）该算法的功能是什么？31.有向图的邻接矩阵类型定义如下： #define MVN 100 最大顶点数 typedef int EType; 边上权值类型 typedef struct EType
10、 edgesMVNMVN; 邻接矩阵，即边表 int n; 图的顶点数MGraph; 图类型例如，一个有向图的邻接矩阵如下所示：阅读下列算法，并回答问题：Void f31(MGraph G) Int i,j,k=0; Step1: for (i=0; iG.n; i+) for (j=0; jG.n; j+) if (G.edgesij= =1) k+; printf(“%dn”,k); step2: for (j=0; jG.n; j+) k=0; for (i=0; iG.n; j+) if (G.edgesij= =1) k+; printf(“%dn”,k); (1)stepl到ste
11、p2之间的二重循环语句的功能是什么? (2)step2之后的二重循环语句的功能是什么?32阅读下列算法，并回答问题： void f32(int r， int n) Int i，j； for (i=2；in；i+) r0=ri； j=i-l； while (r0rj) rj+l=rj； j=j-1； rj+l=r0； (1)这是哪一种插入排序算法?该算法是否稳定? (2)设置r0的作用是什么?33顺序表类型定义如下： typedef int SeqList100； 阅读下列算法，并回答问题： void f33(SeqList r， int n) int a, b，i； if (r0 else a
12、=r1； b=r0； for (i=2；in；i+) if (rib) b=ri； printf(a=d，b=d。n，a，b)； (1)给出该算法的功能； (2)给出该算法的时间复杂度。五、算法设计题(本题10分)34二叉树的存储结构类型定义如下 typedef struct node int data； struct node *lchild， *rchild； BinNode；typedef BinNode *BinTree； 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *s
13、um) *count和*sum的初值为0。2012年1月高等教育自学考试全国统一命题考试数据结构 试题课程代码：02331考生答题注意事项：1. 本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。2. 第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3. 第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹笔作答。4. 合理安排答题空间，超出答题区域无效。一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.每个结点有且仅有一个直接前趋
14、和多个(或无)直接后继(第一个结点除外)的数据结构称为A.树状结构B.网状结构C.线性结构D.层次结构2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是A.单链表B.双链表C.仅有头指针的单循环链表D.仅有尾指针的单循环链表3.已知一个栈的入栈序列是1，2，3，n，其输出序列为pl，p2，p3.，pn，若p1是n，则pi是A.iB.n-iC.n-i+lD.不确定4.下面关于串的叙述中，正确的是A.串是一种特殊的线性表B.串中元素只能是字母C.空串就是空白串D.串的长度必须大于零5.无向完全图G有n个结点，则它的边的总数为A.n2B.n(n-1)
15、C.n(n-1)/2D.(n-1)6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是A.9B.11C.15D.不确定7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是A.acfdebB.aebdfcC.aedfbcD.aefdbc8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是A.快速排序B.归并排序C.冒泡排序D.直接选择排序9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是A.按层遍历B.前序遍历C.中序遍历D.后序遍历10.用ISAM和VSAM组织的文件都属于A.散列文件B.索引顺序文件C.索引非顺序文件D.多关键字文
16、件11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是A.选择B.快速C.希尔D.冒泡12.当采用分块查找时，数据的组织方式为A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序，块间是否有序均可D.数据分成若干块，每块内数据不必有序，但块间必须有序13.下述编码中不是前缀码的是A.(00，01，10，11)B.(0，1，00，11) C.(0，10，110，111)D.(1，01，000，001)14.若一个栈以向量V1.n存储，初始栈顶指针top为n
17、+l，则x进栈的正确操作是A.top=top-1；Vtop=xB.Vtop=x；top=top+1C.top=top+1；Vtop=xD.Vtop=x；top=top-115.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是A.p - data = - 1B.p - next = NULLC.p - next - next=headD.p - next = head二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)请在每个空格中填上正确答案。错填、不填均无分。16.在数据的逻辑结构和存储结构中，与计算机无关的是_。17.线性表L=(a1,
18、a2,，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有front=11，rear=29；front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是_和_。19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_。20.已知三对角矩阵A1010的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A67 的地址为_。21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长
19、度是_。22.有向图G如图所示，它的两个拓扑排序序列分别为_和_。23.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。24.已知广义表A=(x，(a，b)，c，)，函数head(head(tail(A)的运算结果是_。25.索引顺序文件既可以顺序存取，也可以_。三、解答题(本大题共4小题，每小题5分，共20分)26.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。初始堆：第一趟：第二趟：27.设散列函数为H (key)=key 11，散
20、列地址空间为010，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。29.已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。四、算法阅读题(本大题共4小题，每小题5分，共20分)30.阅读下列算法，并回答下列问题：(1)简述该算法的功能；(2)写出分别输入字符串：abcba和abcbde，调用算法函数的返回值。int
21、 symmetry(void) int i=0,j,k；.char str80；SeqStack s；InitStack(&s)；gets (str)；while (stri!= 0) i+；for (j=0;ji/2.j+)push(&s,strj)；if (i2!=0) k=i/2+1；else k=i2；for (j=k;ji;j+)if (strj!=pop(&s)return 0；return 1；(1)(2)31.下列算法是利用二分查找方法在递减有序表R中插入元素x，并保持表R的有序性。请在空缺处填入适当的内容，使其成为一个完整的算法。typedef struct KeyType
22、key；InfoTyep otherinfo； RecType；typedef RecType SeqList Maxlenvoid BinInsert(SeqList R,int *n，RecType x) int low=1，high=*n；int mid，i;while (lowRmid.key) (1) ；else (2) ；for (i=*n；i=low；i-)Ri+1=Ri； (3) ； +(*n)；(1)(2)(3)32.阅读下列算法，并回答下列问题：(1)简述该算法中标号s1所指示的循环语句的功能；(2)简述该算法中标号s2所指示的循环语句的功能。LinkList Insert
23、mnode(LinkList head，char x，int m)LinkNode*p，*q，*s;int i; char ch；p=head-next；s1：while (p&p-data!=x)p=p-next；if (p=NULL)printf(errorn)；else q=p-next；s2： for(i=1；idata=ch；p-next=s；p=s；p-next=q；return head；(1)(2)33.阅读下列算法，并回答下列问题：(1)该算法采用的是何种排序方法?(2)算法中的Rn+1的作用是什么?typedef struct KeyType key；InfoType ot
24、herinfo；RecType；typedef RecType SeqListMaxLen；void sort(SeqList R，int n) /n=1;k-)if (Rk.keyRk+l.key)Rn+1=Rk；for (i=k+1；Ri.keyRn+1.key;i+)Ri-1=Ri;Ri-l=Rn+1；(1)(2)五、算法设计题(本题10分)34.假设以单链表表示线性表，单链表的类型定义如下：typedef struct node DataType data；Struct node *next； LinkNode，* LinkList；编写算法，在一个头指针为head且带头结点的单链表中
25、，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode (LinkList head，DataType x)全国2011年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1、在数据的逻辑结构中，树结构和图结构都是（ ）A.非线性结构B.线性结构C.动态结构D.静态结构2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ）A.O（1）B.（log n）C.O（n）D.O（n2）3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ）A.p1next=p2next;p2next=p1next;B. p2next=p1next;p1next=p2next;C. p=p2next; p1next=p;p2next=p1next;D. p=p1next; p1next= p2next；p2next=p;4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（ ）A.2个B.3个C.4个D.6个5.队列的特点是（
