自考数据结构02331历年试题及答案(2009--2015个人整理版)
全国2009年1月自学考试数据结构试题
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下列程序段的时间复杂度为( )9 s=0；
for(i=1；i B.O(n) D.O(n2) B.head->next==NULL； D.head->next==head； B.后进先出 D.出优于进 2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( )22 3.栈是一种操作受限的线性结构，其操作的主要特征是( )32 4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n C.(front-rear+1)％n 5.判断两个串大小的基本准则是( )52 A.两个串长度的大小 C.两个串中大写字母的多少 素A[3][2]的存储地址为( )60 A.1012 C.1034 a00 7.高度为5的完全二叉树中含有的结点数至少为( )72 A.16 C.31 A.5 B.17 D.32 B.8 a01 a02 a32 B.1017 D.1036 a03 a04 B.两个串中首字符的大小 D.对应的第一个不等字符的大小 B.(rear-front)％n D.(rear-front+n)％n 6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元 8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) 专业word可编辑 . .. .. .. C.11 D.18 9.下列所示各图中是中序线索化二叉树的是( A )81A 10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( )108 A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3) 11.如图所示有向图的一个拓扑序列是( ) A.ABCDEF B.FCBEAD C.FEDCBA D.DAEBCF 12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 C.9，8，6，3，5，l，2，7 数的平均值为( )172 A.C. B.9，8，1，7，5，6，2，33 D.9，8，6，7，5，1，2，3 13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次 39 15B. 49 155155 D. 151514.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( D )d 197 15.数据库文件是由大量带有结构的( )206 A.记录组成的集合 C.数据项组成的集合 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的____输入量_____。 8 17.在双向循环链表中插入一个新的结点时，应修改_____4____个指针域的值。 28 ．．． 专业word可编辑 . B.字符组成的集合 D.数据结构组成的集合 .. .. .. 18.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现___5______个不同的出栈序列。5 19.链串的结点大小定义为结点的_____数据域____中存放的字符个数。 54 20.广义表(a，(d，(c)))的深度为___3 ______。67 21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有____4_____棵。4 22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。第i列非零元素的个数107 23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。 15，12，11，10，8，16，18，17 24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_____起始位置____构成。173 25.VSAM文件的实现依赖于操作系统中的_____分页____存取方法的功能。 215 三、解答题(本大题共4小题，每小题5分，共20分) 26.假设有一个形如 的8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。 若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题： (1)B数组的体积至少是多少? (2)若a18存储在B[0]中，a56存储在B[k]中，则k值为多少? (1) （1+8）*8/2=36 存放次对角线以上的零为37 (2) 12 27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。 (1)写出排序过程中前两趟的划分结果； (2)快速排序是否是稳定的排序方法? (1) 第一趟划分结果；(2，3，1)，5，(9，6，8，7) 第二趟划分结果；(1，2，3)，5，(9，6，8，7) 第三趟划分结果；(1，2，3)，5，(7，6，8，9) 第四趟划分结果； 1，2，3，5，6，7，8，9 第一趟划分过程 2 3 1 5 9 6 8 7 专业word可编辑 . .. .. .. 1 1 2 2 3 3 5 5 9 7 6 6 8 8 7 9 1 2 (5，8，1，3，9，6，2，7) 1．(2，8，1，3，9，6，5，7) 2．(2，5，1，3，9，6，8，7) 3．(2，3，1，5，9，6，8，7) 4．(2，3，1，5，9，6，8，7) 第二趟划分过程 (2，3，1，5，9，6，8，7) 1．(1，2，3，5，7，6，8，9) (2)非稳定 3 5 6 7 8 9 ↑j ↑i 2 1 2 3 3 1 5 5 5 7 5 9 6 6 6 8 7 ↑j 8 9 8 7 9 专业word可编辑 . .. .. .. ↑i 第一趟：（2，3，1）5 （9，6，8，7） 第二趟： 1，2，3，5 （9，6，8，7） 第三趟：1，2，3，5，（7，6，8），9 第四趟：1，2，3，5，6，7，8，9 28.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求： (1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)； (2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。 (1) 专业word可编辑 . .. .. .. (2) 29.已知3阶B—树如图所示， 非根 【1，2】P184 根 【1，2】 (1)画出将关键字6插入之后的B—树； 5,8 1,3 6 9 (2)画出在(1)所得树中插入关键字2之后的B—树。 专业word可编辑 . 5,8 5,8 1,2,3 1,3 6 9 6 9 2,5,8 1,2,3 6 9 .. .. .. 四、算法阅读题(本大题共4小题，每小题5分，共20分) 30.假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 阅读下列算法，并回答问题： (1)已知初始链表如图所示，画出执行f30(head)之后的链表； 1 3 6 9 2 8 5 1 3 2,5,8 6 9 题30图 (2)简述算法f30的功能。 void f30( LinkList head) { LinkList p,r, s; if (head - > next) { r = head - > next; p = r->next; r - > next = NULL; 专业word可编辑 . .. .. .. while (p) { s =p; p = p->next; if ( s - > data% 2 = = 0) { s - > next = head - > next; head - > next = s; } else { s - > next = r - > next; r->next = s; r =s; } } } } (1)(2) 2 8 5 7 31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { DataType data; struct node * lchild, * rchild; //左右孩子指针 } * BinTree ; 阅读下列算法，并回答问题： (1)已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值； (2)简述算法f31的功能。 int f31 ( BinTree T) { int d; if ( ! T) return 0; d = f31 ( T - > lchild) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else return d; (1)3 (2)统计度为2的结点个数 32.设有向图邻接表定义如下： 专业word可编辑 . .. .. .. typedef struct { VertexNode adjlist[ MaxVertexNum ] ; int n，e； ／／图的当前顶点数和弧数 }ALGraph； ／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为： 阅读下列算法，并回答问题： (1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(＆G)的输出； (2)简述算法f32的功能。 int visited[ MaxNum ]; void DFS(ALGraph * G, int i) { EdgeNode * p; visited [ i ] = TRUE ; if (G - > adjlist[ i]. firstedge = = NULL) printf( \"% c \； else { p = G - > adjlist[ i]. firstedge; while (p ! = NULL) { if ( ! visited[p -> adjvex] ) DFS( G, p - > adjvex) ; p = p->next; } } } void f32 ( ALGraph * G) { int i; for (i = 0; i < G->n; i ++) visited [ i ] = FALSE ; for (i = 0; i < G->n; i++) if ( ! visited[i] ) DFS(G, i) ; } (1)ABECD (2)图的深度优先搜寻 专业word可编辑 A B E C . D .. .. .. 33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。 #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType ; typedef NodeType SqList[ MAXLEN ]; void f33 ( SqList R, int n) { int i,j,k; NodeType t; i =0; j =n-l; while (i < j) { for ( (1) ) k=i;k for (k =j; k > i; k -- ) if ( (2) ) { R[k].key < R[k-l].key t = R[k]; R[k] = R[k-1]; R[k-1] = t; } (3) ; i++ } } 专业word可编辑 . .. .. .. (1) (2) (3) 五、算法设计题(本大题10分) 34.假设以带头结点的单链表表示线性表，单链表的类型定义如下： typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为： void f34(LinkList head) { LinkNode *p,*max,*q; P=head->next; max=head->next; while(P) { P=p->next; If(p->data>max->data) max=p; } x=max->data; } } delete_L(Lnode *L,int i) {Lnode *p,*q; int j; Elemtype x; P=L;j=0; While(p->next!=null&&j<=i-1) {p=p->next;j++;} 专业word可编辑 . .. .. .. If(! P->next||i<1) { Printf(\"\\n删除位置错误！\");return(-1);} Else{q=p->next;x=q->data; P->next=q->next;free(q); Return(x); } }/*delete_L*/ 全国2009年10月自学考试数据结构真题 一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项 中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均 无分。 1. 按值可否分解，数据类型通常可分为两类，它们是(c) A. 静态类型和动态类型 B. 原子类型和表类型 C. 原子类型和结构类型 D. 数组类型和指针类型 2. D h(n)是0(n2) 答案：C A. B. C. D. A f(n)是0(g(n)) B g(n)是0(f(n)) C h(n)是0(nlogn) 3. 指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程 序段是() p->next=r；r->next=q；q->next=r->next； r->next=q；q->next=r->next；p->next=r； r->next=q；p->next=r；q->next=r->next； 答案：A A. B. C. D. p->next=r；q->next=r->next；r->next=q； 4. 若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列 专业word可编辑 . .. .. .. 个数是() 5 6 7 答案：B A. B. C. D. 3 5. 假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指 针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为() (rear+1)％n==front 答案：D A. B. C. D. rear==front (front+1)％n==rear rear+1==front 6. 串的操作函数str定义为： 3 4 5 6 答案：C A. B. C. D. 7. 二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素 A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为() 1024 1036 1240 答案：A A. B. C. D. 1020 8. 对广义表L= (a，())执行操作tail(L)的结果是() A. () B. (()) C. a D. (a) 答案：B 9. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为() A. FEDCBA 专业word可编辑 . .. .. .. B. ABCDEF C. FDECBA D. FBDCEA 答案：A 10. 已知森林F={T1，T2，T3，T4，T5}，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别 为7，3，5，1，2，则与F对应的二叉树的右子树中的结点个数为() 3 8 11 答案：D A. B. C. D. 2 11. 若非连通无向图G含有21条边，则G的顶点个数至少为() A. 7 B. 8 C. 21 D. 22 答案：B 12. 如图所示的有向图的拓扑序列是() A. c，d，b，a，e B. c，a，d，b，e C. c，d，e，a，b D. c，a，b，d，e 答案：B 13. 对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划 分的结果为() (8，7，6，5，4，3，2，1) 答案：C A. B. C. D. (5，1，4，3，6，2，8，7) (5，1，4，3，2，6，7，8) (5，1，4，3，2，6，8，7) 专业word可编辑 . .. .. .. 14. 分块查找方法将表分为多块，并要求() A. 块内有序 B. 块间有序 C. 各块等长 D. 链式存储 答案：B 15. 便于进行布尔查询的文件组织方式是() A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 答案：D 二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请 在每个空格中填上正确答案。错填、不填均无分。 1. 数据的链式存储结构的特点是借助_指针__表示数据元素之间的逻辑关系。 2. 如果需要对线性表频繁进行_插入__或__删除_操作，则不宜采用顺序存储结构。 3. 如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是 top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是_ top1>top2(或top2=top1-1或top1=top2+1)。 4. 静态存储分配的顺序串在进行插入、置换和__联接_等操作时可能发生越界。 5. 广义表L=（a，（b，( )））的深度为_3__。 6. 任意一棵完全二叉树中，度为1的结点数最多为_1__。 7. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_边__的数目正相关。 专业word可编辑 . .. .. .. 8. 在5阶B树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含_2__个关键字。 9. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_稳定__的。 10. 常用的索引顺序文件是__ ISAM _文件和_ VSAM __文件。 三、解答题(本大题共4小题，每小题5分，共20分) 1. 答案： 2. 由字符集{s，t，a，e，i}及其在电文中出现的频度构建的哈夫曼树 如图所示。 已知某段电文的哈夫曼编码为111000010100， 请根据该哈夫曼树进行译码，写出原来的电文。 答案：eatst(说明：每个字母1分)（5分） 3. 已知无向图G的邻接表如图所示， (1)画出该无向图； 专业word可编辑 . .. .. .. (2)画出该图的广度优先生成森林。 4. 对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根 )堆及前两趟重建堆之后的序列状态。 初始堆： 第1趟： 第2趟： 答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分） 第1趟：（63，55，50，48，22，31，11，37，96）（2分） 专业word可编辑 . .. .. .. 第2趟：（55，48，50，37，22，31，11，63，96）（1分） 四、算法阅读题(本大题共4小题，每小题5分，共20分) 1. 阅读下列算法，并回答问题： (1)无向图G如图所示，写出算法f30(&G)的返回值； (2)简述算法f30的功能。 #define MaxNum 20 int visited［MaxNum］； void DFS(Graph *g，int i)； /*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited［j］为1*/ int f30(Graph *g) {int i，k； for (i=0； i for (i=k=0； i DFS(g，i)； } return k； } (1) (2) 答案：（1）3（3分） （2）返回无向图g中连通分量的个数。（2分） 2. 假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node { int id;/*学号*/ int score；/*成绩*/ struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (2)简述算法f31的功能。 void f31(LinkList A, LinkList B) {LinkList p, q; p=A->next; q=B->next; while (p && q) {if (p->id 专业word可编辑 . .. .. .. p=p->next; else if (p->id >q->id) q=q->next; else { if (p->score <60) if (q->score <60) p->score=q->score; else p->score=60; p=p->next; q=q->next; } } } (1) (2) 答案： 专业word可编辑 . .. .. .. 3. 阅读下列算法，并回答问题： (1)设串s=＂OneWorldOneDream＂，t=＂One＂，pos是一维整型数组，写出算法 f32(s，t，pos)执行之后得到的返回值和pos中的值； (2)简述算法f32的功能。 int strlen(char*s)； /*返回串s的长度*/ int index(char*st，char*t)； ／*若串t在串st中出现，则返回在串st中首次出现的 下标值，否则返回-1*/ int f32(char*s, char*t, int pos［］) { int i, j, k, ls, lt; ls=strlen(s); lt=strlen(t); if (ls==0||lt==0) return-1; k=0; i=0; do { j=index(s+i, t); if (j>=0) { pos［k++］=i+j; i+=j+it; } }while(i+it<=is && j >=0 return k; } (1) (2) 专业word可编辑 . .. .. .. 答案：（1）2；pos［0］=0,pos［1］=8(说明：每个值1分)（3分） （2）返回串t在s中出现的次数，并将每次出现的位置依次存放在数组pos中。（2分） 4. 二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node { KeyType key;/*关键字项*/ InfoType otherinfo;/*其它数据项*/ struct node *lchild, *rchild;/*左、右孩子指针*/ } BSTNode, *BSTree； 阅读算法f33，并回答问题： (1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字； (2)在哪些情况下算法f33返回空指针? (3)简述算法f33的功能。 BSTNode *f33(BSTree T, KeyType x) { BSTNode *p; if (T==NULL) return NULL; p=f33(T->lchild, x); if (p!=NULL) return p; if (T->key >x) return T; return f33(T->rchild, x); } (1) (2) (3) 答案：（1）10（2分） （2）T是空树或T中所有结点的关键字均不大于给定值x时，返回空指针。（2分） （3）如果二叉排序树T中存在含有关键字大于给定值x的结点，则返回指针指向它们中关键字最 小的结点，否则返回空指针。（1分） 五、算法设计题（本题10分） 1. 假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct { int data［ListSize］; int length; } SeqList, *Table; 编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 答案：参考答案一： void f34(Table L)(或者参数说明为：SeqList *L,1分) { int i,j,t; 专业word可编辑 . .. .. .. i=0;（初始化，1分） j=L->length-1; while(i while(i if(i } }(其他，如“L->”表达，1分) } 参考答案二： void f34(SeqList*L)(或者参数说明为：Table L,1分) { int i,j=0,t;(初始化，1分) for(i=0;i if(L->data［i］%2)/*奇数*/（奇数处理框架，1分） { if(i!=j)(避免同一元素交换，1分) { t=L->data［i］;(交换，2分) L->data［i］=L->data［j］; L->data［j］=t; j++;（1分） }（其他，如“L->”表达，1分） } 全国2010年1月自学考试数据结构试题 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ） A．问题规模 C．循环层数 B．语句条数 D．函数数量 专业word可编辑 . .. .. .. 2．具有线性结构的数据结构是（ C ）线性结构有：顺序表、栈和队列、串 A．树 C．栈和队列 B．图 D．广义表 3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ） A．O(1) C．O(n) B．O(m) D．O(m+n) 插入到长度为m的单链表，需找到表尾，时间复杂度为o(m)，连接的时间复杂度为0(1),所以总的时间复杂度为0(m) 4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ） A．2个 C．4个 B．3个 D．6个 void DInsertBefore(DListNode *p,DataType x)//在带头结点的双链表中，将值为x的新结点插入结点*p之前，设p≠NULL {DListNode *s=malloc(sizeof(ListNode));① s->data=x;②s->prior=p->prior; ③s->next=p;④p->prior->next=s;⑤p->prior=s; } ⑥ 5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 C．50 B．37 D．97 对于循环向量中的循环队列，写出通过队头队尾指针表示的队列长度公式。（front指向实际队头，rear指向实际队尾的下一元素位置。）当rear≥front时，队列长度L=rear-front；当rear .. .. .. D．不需要判断栈满也不需要判断栈空 因为链栈中的结点是动态分配的，可以不考虑上溢，所以无需定义stackFull运算。 7．若串str=”Software”，其子串的数目是（ D ） A．8 C．36 B．9 D．37 8．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ） A．1012 C．1032 B．1017 D．1039 在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0≤i 若a44为第一个元素， a85与a00为第一个元素时的a(85-(44-00))= a41位置一样，k=4*5/2+1=11，则a85的地址=1000+11=1011； 9．允许结点共享的广义表称为（ D ） A．纯表 C．递归表 B．线性表 D．再入表 10．下列数据结构中，不属于二叉树的是（ A ） A．B树 B树是一种平衡的多叉树 C．二叉排序树 B．AVL树 AVL树是自平衡二叉查找树 D．哈夫曼树 哈夫曼树是最优二叉树 11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） ．． 专业word可编辑 . .. .. .. A．1，5，2，6，3，4 C．5，1，6，3，4，2 B．1，5，6，2，3，4 D．5，1，2，6，4，3 12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ） A．v1，v2，v3，v4，v5，v6，v7 C．v1，v2，v3，v4，v7，v5，v6 B．v1，v2，v5，v4，v3，v7，v6 D．v1，v2，v5，v6，v7，v3，v4 深度优先遍历类似于树的前序遍历。其特点是尽可能先对纵深方向进行搜索。 13．下列排序算法中不稳定的是（ A ） A．快速排序 C．冒泡排序 B．归并排序 D．直接插入排序 稳定：直接插入、冒泡、归并、基数 不稳定：直接选择、希尔、快速、堆 14．一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值32 时，查找成功需要的比较次数是（ B ）mid1=45，mid2=9，mid3=32 A．2 C．4 B．3 D．8 15．采用ISAM组织文件的方式属于（ D ） A．链组织 C．散列组织 B．顺序组织 D．索引组织 专业word可编辑 . .. .. .. 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据元素及其关系在计算机存储器内的表示称为__存储结构_______。 17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___O（ n）______。 18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是____取栈顶_____。 typedef struct{ DataType data[100]； int top； }SeqStack； DataType f18(SeqStack*S) { if(StackEmpty(S)) Error(”Stack is empty”)； return S->data[S->top]； } 19．在串匹配中，一般将主串称为目标串，将子串称为___模式串______。 20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))= ___()______。 21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为 ___221______。 WPL=30×1+18×2+16×3+13×4+6×5+7×5=30+36+48+52+30+35=231 22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是___35______。 23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是_42,13,94,55,05,46,17。 24．高度为3的3阶B-树最少的关键字总数是__5_______。P182 专业word可编辑 . .. .. .. 一颗m（m≥3）阶的B-树，每个非根结点中所包含的关键字个数j满足：┌ m/2 ┐-1≤j≤m-1。即每个非根结点至少应有┌ m/2 ┐-1个关键字，至多有m-1个关键字。 （注：┌ m/2 ┐是指不小于（即大于等于）m/2的最小整数。） 一颗高度为h的m阶B-树中最少可容纳的关键字总数为：┌ m/2 ┐h-1，最少可容纳的结点总数为 ┌ m/2 ┐h-1 ┌ m/2 ┐-1 以h=3，m=3为例，相应的B-树最少可容纳的关键字总数为┌ m/2 ┐h-1=23-1=7个。 25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是___B+______。 三、解答题(本大题共4小题，每小题5分，共20分) 26．假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。 已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。GCFABDC 27．已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。 请回答下列问题： (1)请画出对应的图G。 (2)画出图G的邻接表存储结构。 vertexfirstedgeadjvexnext012345ABCDEF顶点表101012边表3251344534 28．已知一组待排记录的关键字序列为(16，12，18，60，15，36，14，18，25，85)，用堆排序方法建小根堆， 专业word可编辑 . .. .. .. 请给出初始建堆后的序列。 161612181218601536141815361418116212253188546051563671481892510856011621225318854185156367148609251085i=5，不调整i=4，调整161212141815141636181815361860252153148541851663671886092510856011621225314854185156367188609251085112i=2，不调整i=1，调整i=3，调整 小根堆初始建堆后的序列 29．已知一棵二叉排序树如图所示。 请回答下列问题： (1)画出插入元素23后的树结构； (2)请画出在原图中删除元素57后的树结构。 23 四、算法阅读题(本大题共4小题，每小题5分，共20分) 专业word可编辑 . .. .. .. 30．已知下列程序，Ls指向带头结点的单链表。 Typedefstruct node { DataType data; struct node * next; } * LinkList; void f30( LinkList Ls ) { LinkList p, q; q = Ls->next; if ( q && q->next ) { Ls->next = q->next; p=q while ( p->next ) p = p->next; p->next = q; q->next = NULL; }} 请回答下列问题： (1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。 (2)请简述算法的功能。 删除单链表的中间结点和尾结点。 31．已知字符串处理函数f31程序如下。 int f31(char*strl，char*str2) { while(*strl==*str2&&(*strl!=’＼0’)){ 专业word可编辑 . .. .. .. strl++； str2++； } return(*strl-*str2 ? l∶0)；} 请回答下列问题： (1)若调用语句是f31(”abcde”，”abcdf’)，则函数的返回值是什么?若调用语句是 f31(”abcde”，”abcde”)， 则函数的返回值是什么? 由于'e '对应的ASCII码是101，'f'对应的ASCII码是102，则'e '—'f'=101—102=-1 函数的返回值是1。 函数的返回值是0。 (2)简述该函数的功能。 答：如果两个字符串结点*strl和*strl中的字符相等，且字符串结点*strl中的字符不等于字符串结束标识'\\0'，则两个字符串结点*strl和*strl中的字符指针自加运算。如果条件不满足，则字符串结点*strl和*strl中的字符相减。若逻辑表达式的值为非零，则条件表达式的值等于1；若逻辑表达式的值为零，则条件表达式的值等于0。 32．数组A[]中存储有n个整数，请阅读下列程序。 void f32(intA[]，int n) { inti，j，k，x； k=n-l； while(k>0){ i=k； k=0； for(j=O；j 专业word可编辑 . .. .. .. }／／end of if }／／end of while return； } 请回答下列问题： (1)当A[]={10，8，2，4，6，7}时，执行f32(A，6)后，数组A中存储的结果是什么? 答：数组A中存储的结果是10。 (2)说明该算法的功能。 数组A[]中存储有n个整数，当k=n-1时，则第k个向量是最后一个整数。 当k>0时，即数组A[]非空时，设i=k，k=0，如果j=0，且j KeyType key； InfoType otherinfo； }SeqList[N+1]； int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n； while( (1) low<=high ){ mid=(1ow+high)／2； if( (2) R[mid].key==K ) return mid； if(R[mid]．key>K) 专业word可编辑 . .. .. .. high=mid-1； else (3) low=mid+1 ； } return O； } ／／BinSearch 请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3) 五、算法设计题(本题10分) 34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{ ElmType data； struct Node *lchild，*rchild； }*BiTree； 请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。 求二叉数的结点总数满足如下的递归定义： ①若T为空，则以T为根的二叉树中结点总数为0； ②否则，以T为根的二叉树中结点总数应该是根T的左子树和右子树中结点数之和再加上根本身。 int SumNodes(BiTree T){ //T的初值指向某二叉链表的根结点 if(! T) //T为空 return 0; else 专业word可编辑 . .. .. .. return SumNodes(T->lchild)+ SumNodes(T->rchild)+1; } 全国2010年10月自学考试数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 C.带头结点的双循环链表 B.带头结点的单向链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL C.head!=NULL B.head->next=NULL D.head->next!=head 4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( ) A.n-i C.n-i+2 5.串匹配算法的本质是( ) A.串复制 C.子串定位 B.串比较 D.子串链接 B.n-i+l D.无法确定 6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( ) 专业word可编辑 . .. .. .. A.13 C.33 B.18 D.40 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求两个结点之间的最短路径可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( 专业word可编辑 . ) .. .. .. A.不稳定的 C.基于交换的 B.稳定的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( 15.若需高效地查询多关键字文件，可以采用的文件组织方式为( ) A.顺序文件 B.索引文件 C.散列文件 D.倒排文件 二、填空题（本大题共10小题，每小题2分，共20分） 请每小题的空格中填上正确答案。错填、不填均无分。 16.下面程序段的时间复杂度为______O（n）_____。 sum=1； for（i=0；sum 17.已知链表结点定义如下： typedef struct node{ char data［16］； 专业word可编辑 . ) D .. .. .. struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是_ 4/5_______。 18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为_____99______。 19.3个结点可以组成_____5______种不同树型的二叉树。 20.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是______33_____。 21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为____2m_______。 22.影响排序效率的两个因素是关键字的______比较_____次数和记录的移动次数。 23.对任一m阶的B树，每个结点中最多包含____m-1_______个关键字。 24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为____冲突_______。 25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为____稠密索引_______。 三、解答题（本大题共4小题，每小题5分，共20分） 26.要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答： (1)应该如何设计这两个栈才能充分利用整个向量空间？ (2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则： 栈stackl空的条件是：___________； 栈stack2空的条件是：___________； 栈stackl和栈stack2满的条件是：___________。 27.已知广义表如下： A=(B,y) B=(x，L) L=(a，b) 要求： 专业word可编辑 . .. .. .. (1)写出下列操作的结果 tail(A)=_______________. head(B)=______________。 (2)请画出广义表A对应的图形表示。 28.已知二叉树如下： 请画出该二叉树对应的森林。 29.请回答下列问题： (1)英文缩写DAG的中文含义是什么？ (2)请给出下面DAG图的全部拓扑排序。 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.已知线性表(a1,a2,a3...，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) { int k，m,temp； m= (1) ； while (a［m］<0 &&m 专业word可编辑 . .. .. .. k=m; while (k 31.阅读下列程序，并回答问题： #include substr(char*t,char*s,int pos,int len) { while（len>0&&*s） { *t=*(s+pos-l); t++;s++;len--; } *t='\\0'; 专业word可编辑 . .. .. .. } char *f31(char*s) { char t[100]; if (strlen(s)=1) return s; substr(t,s,1,1); substr(s,s,2,strlen(s)-1); f31(s); return strcat(s,t); } main( ) { char str[100]= ''String''; printf(''%s\\n'',f31(str)); } (1)请写出执行该程序后的输出结果； (2)简述函数f31的功能。 32.下面程序实现插入排序算法。 typedef struct{ int key; Info otherinfo; }SeqList; void InsertSort(SeqList R［］,int n) {/* 待排序列保存在R［1..n］中*/ SeqList x； int i，j，k，lo,hi,mi; 专业word可编辑 . .. .. .. for (i=2；i<=n；i++) { (1) ； lo=1； hi=i-l; while (lo<=hi) { mi=(lo+hi)/2; if ( (2) ) break; if (R［mi］.key>x.key) hi=mi-l; else lo=mi+l; } if (mi=lo) k=i - mi; else k=i - mi-1; for (j=0；j 在空白处填写适当的内容，使该程序功能完整。 (1) (2) (3) 33.设有单链表类型定义如下： typedef struct node { 专业word可编辑 . .. .. .. int data; struct node *next; } *LinkList; 阅读下列算法，并回答问题： void f33(LinkList head, int A, int B) { LinkList p=NULL; While (head !=NULL) { if (head->data>A&&head->data if (p !=NULL) printf(\"%d\\n\ } (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果； (2)简述算法f33的功能。 五、算法设计题（本题10分） 34.已知二叉树的定义如下： typedef struct node{ int data; struct node *lchild, *rchild; }*Bitptr； 专业word可编辑 . .. .. .. 编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）； 专业word可编辑 . .. .. .. 全国2011年1月自学考试数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 专业word可编辑 . .. .. .. 1.下列选项中与数据存储结构无关的术语是（ ） A.顺序表 C.链队列 B.链表 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ） A.n-1 C.2n-1 B.n D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ ） A.rear=(rear-1)%m; C.front=(front-1)%m; B.front=(front+1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（ ） A.堆栈 C.队列 B.多维数组 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（ ） A.求子串 C.串匹配 B.串联接 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（ ） A.( ) C.(( ),( )) B.(( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ ） A.结点均无左孩子的二叉树 C.高度为n的二叉树 B.结点均无右孩子的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ ） A.4 C.7 B.5 D.8 专业word可编辑 . .. .. .. 9.下列叙述中错误的是（ ） A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ B.V1,V3,V2,V4 D.V1,V2,V4,V3 11.平均时间复杂度为O(n log n)的稳定排序算法是（ ） A.快速排序 C.归并排序 B.堆排序 D.冒泡排序 12.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（ ） A.(18,22,30,46,51,68,75,83) C.(46,30,22,18,51,75,68,83) B.(30,18,22,46,51,75,83,68) D.(30,22,18,46,51,75,68,83) 13.某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（ ）[[(2+80)/2+(3+81)/2+(4+82)/2+(5+83)/2+(6+84)/2]*79]/395 A.43 C.198 B.79 D.200 14.在含有10个关键字的3阶B-树中进行查找，至多访问的结点个数为（ ） A.2 C.4 B.3 D.5 15.ISAM文件系统中采用多级索引的目的是（ ） 专业word可编辑 . .. .. .. A.提高检索效率 C.减少数据的冗余 B.提高存储效率 D.方便文件的修改 二、填空题（本大题共10小题，每小题2分，共20分） 16.数据结构由数据的逻辑结构、存储结构和数据的_______运算_____三部分组成。 17.在单链表中某结点后插入一个新结点，需要修改_______2________个结点指针域的值。 18.设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是________3________。 19.长度为零的串称为______空串__________。 20.广义表G=(a,b，(c，d，(e，f))，G)的长度为____4____________。 21.一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是_______左子树为空_________。 22.一个有n个顶点的无向连通图，最少有______n-1__________条边。 23.当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是____直接插入排序____。 24.在一棵深度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是___h___________。 25.不定长文件指的是文件的____记录________大小不固定。 三、解答题（本大题共4小题，每小题5分，共20分） 26.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG， 请回答下列问题： (1)画出此二叉排序树； (2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。 27.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵； (2)从结点A出发，写出该图的深度优先遍历序列。 专业word可编辑 . .. .. .. 28.已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题： (1)画出堆排序的初始堆（大根堆）； (2)画出第二次重建堆之后的堆。 29.已知关键字序列为(56，23，41，79，38，62，18)，用散列函数H(key)=key%11将其散列到散列表HT[0..10]中，采用线性探测法处理冲突。请回答下列问题： (1)画出散列存储后的散列表： (2)求在等概率情况下查找成功的平均查找长度。 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列程序。 void f30(int A[]， int n) { int i,j,m; for (i=1；i } 回答下列问题： 1 2 3(1)已知矩阵B= 4 5 6，将其按行优先存于一维数组A中，给出执行函数调 7 8 9 专业word可编辑 . .. .. .. 用f30(A，3)后矩阵B的值； (2)简述函数f30的功能。 31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data; struct node*Ichild, *rchild; ∥左右孩子指针 } *BinTree； 阅读下列程序。 void f31(BinTree T) { InitStack(S); ∥ 初始化一个堆栈S while (T || !StackEmpty(S) { while (T) { Push(S,T); T=T->lchild; } if (!StackEmpty(S)) { T=Pop(S); printf(“%c”,T->data); T=T->rchild; } } } 回答下列问题： (1)已知以T为根指针的二叉树如图所示， 专业word可编辑 . .. .. .. 请写出执行f31(T)的输出结果： (2)简述算法f31的功能。 32.阅读下列程序。 void f32(int A[],int n) { int i,j,m=l,t； for (i=0; i t=A[j-l]; A[j-1]=A[j]； A[j]=t； m=1； } } } 回答问题： 已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。 33.已知顺序表的表结构定义如下： 专业word可编辑 . .. .. .. #define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType； typedef NodeType SqList[MAXLEN]; 阅读下列程序。 Int f33(SqList R，NodeType X, int p, int q) { int m; if (p>q) return -1; m=(p+q)／2； if (R[m].key==X.key) return m; if (R[m].key>X.key) return f33(R,X,p,m-l); else return f33(R,X,m+l,q); } 请回答下列问题： (1)若有序的顺序表R的关键字序列为(2,5，13,26,55,80,105)，分别写出X.key=18和X.key=26时，执行函数调用f33(R,X,0,6)的函数返回值。 (2)简述算法f33的功能。 五、算法设计题（本题10分） 34.假设用带头结点的单循环链表表示线性表，单链表的类型定义如下： typedef struct node { int data; struct node*next; 专业word可编辑 . .. .. .. }LinkNode，*LinkList; 编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为： float f34(LinkList head): 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 全国2011年10月自学考试数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1、在数据的逻辑结构中，树结构和图结构都是（ ） A.非线性结构 B.线性结构 专业word可编辑 . .. .. .. C.动态结构 D.静态结构 2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ） A.O（1） C.O（n） B.Ｏ（log n） D.O（n2） 3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ） A.p1－＞next=p2－＞next;p2－＞next=p1－＞next; B. p2－＞next=p1－＞next;p1－＞next=p2－＞next; C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p; 4.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（ ） A.2个 C.4个 5.队列的特点是（ ） A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入，在另一端进行删除 6.一个链串的结点类型定义为 ﹟define NodeSize 6 typedef struct node{ char data[NodeSize]; struct node*next; }LinkStrNode; B.3个 D.6个 专业word可编辑 . .. .. .. 如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（ ） A.1/3 C.2/3 B.1/2 D.3/4 7.广义表A=（a,B,(a,B,(a,B,……）））的长度为（ ） A.1 C.3 B.2 D.无限值 8.已知10×12的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为（ ） A.470 C.472 B.471 D.473 9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ） A.12 C.18 B.16 D.20 10.在带权图的最短路径问题中，路径长度是指（ ） A.路径上的顶点数 C.路径上的顶点数与边数之和 B.路径上的边数 D.路径上各边的权值之和 11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ） A.e C.n2-2e B.2e D.n2-1 12.要以O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ ） A.归并排序 C.堆排序 B.快速排序 D.冒泡排序 13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（ ） A.堆排序 C.冒泡排序 B.快速排序 D.归并排序 专业word可编辑 . .. .. .. 14.对有序表进行二分查找成功时，元素比较的次数（ ） A.仅与表中元素的值有关 C.仅与被查元素的值有关 15.散列文件是一种（ ） A.顺序存取的文件 C.索引存取的文件 B.随机存取的文件 D.索引顺序存取的文件 B.仅与表的长度和被查元素的位置有关 D.仅与表中元素按升序或降序排列有关 二、填空题（本大题共10小题，每小题2分，共20分） 16.若一个算法中的语句频度之和为T（n）=3n3-200nlog2n+50n，则该算法的渐近时间复杂度为___O(n^3)_______. 17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由___前驱节点的链指针__________指示。 18.栈的修改是按____后进先出______的原则进行。 19.字符串中任意个连续的字符组成的子序列称为该串的___子串_______。 20.假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=___34_______。k=10+9+8+7+1-1=34 21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为__0________。 22.对于稀疏图，采用_____邻接表_____表示法较为节省存储空间。 23.在排序过程中，如果____需要在内外存之间交换数据_________，则称其为外部排序。 24.设有一组记录的关键字为｛19，14，23，1，68，12，10，78，25｝，用链地址法构造散列表，散列函数为h（key）=key％11,散列地址为1的链中有____4______个记录。 25.多关键字文件的特点是除主文件和主索引外，还建有____次关键字索引______。 三、解答题（本大题共4小题，每小题5分，共20分） 26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始） 0080000710000000500 000629（1）画出三元组表； 专业word可编辑 . .. .. .. （2）画出三元组表的行表。 (1) (2) 27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。 （1）画出该森林； （2）画出该森林所对应的二叉树。 (1) (2) 28.对关键字序列（429，653，275，897，170，908，473，256，726）进行基数排序，写出每一趟的排序结果。 29.对下列关键字序列 （87，25，310，08，27，132，68，96，187，133，70，63，47，135） 构造散列表，假设散列函数为h（key）=key％13,用拉链法解决冲突。 （1）画出该散列表； （2）求等概率情况下查找成功的平均查找长度ASL; （3）写出删除值为70的关键字时所需进行的关键字比较次数。 (1) (2) (3) 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列算法，并回答问题： （1）假设L=（3，7，7，11，20，20，20，51，51），写出执行函数f30（&L）后的L； （2）简述f30的功能。 void f30(SeqList*L) { ∥L为非空的有序表 int i=1,k=0; 专业word可编辑 . .. .. .. while(i＜L－＞length） ｛ if(L－＞data[i]!=L－＞data[k]) L－＞data[++k]=L－＞data[i]; i++; } L－＞length=k+1； } (1) (2) 31.阅读下列算法，并回答问题： （1）假设栈S=（3，8，6，2，5），其中5为栈顶元素，写出执行函数f31（&S）后的S； （2）简述函数f31的功能。 void f31(Stack *S){ Queue Q；InitQueue(&Q); while(!StackEmpty(S)) EnQueue(&Q,Pop(&S)); while(!QueueEmpty(Q)) Push(&S,DeQueue(&Q)); } （1） （2） 32.假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题： （1）若向量BT为： 专业word可编辑 . .. .. .. A B C D E F G 1 2 3 4 5 6 7 画出执行函数f32（BT,7,1）的返回结果; (2)简述函数f32的功能。 BinTree f32(DataType BT[],int n,int i) { BinTree p; if (i＞n) return NULL; p=（BinTNode*）malloc(sizeof(BinTNode)); p－＞data=BT[i]; p－＞lchild=f32(BT,n,i*2); p－＞rchild=f32(BT,n,i*2+1); return p; } (1) (2) 33.已知有向图的邻接表和邻接矩阵定义如下： ﹟define MaxNum 50 typedef struct node { int adjvex; struct node *next; } EdgeNode; typedef struct{ char vertex； 专业word可编辑 ∥图的最大顶点数∥邻接点域 ∥链指针域 ∥边表结点结构 ∥顶点域 . .. .. .. EdgeNode *firstedge; } VertexNode; typedef struct { VertexNode adjlist [MaxNum]; int n,e; } ALGraph; typedef struct{ char vertex[MaxNum]; ∥边表头指针 ∥顶点表结点结构 ∥邻接表 ∥图中当前顶点数和边数 ∥邻接表描述的图 ∥顶点表 ∥邻接矩阵 ∥图中当前顶点数和边数 ∥邻接矩阵描述的图 int adjmatrix [MaxNum][MaxNum]; int n,e; } AMGraph; 下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整： void f33（ALGraph G1,AMGraph *G2） { int i, j; EdgeNode *p; G2－＞n=G1.n; G2－＞e= (1) ; for (i=0; i＜G1.n; i++) { G2－＞vertex[i]= (2) ; p=G1.adjlist[i].firstedge; for (j=0; j＜G1.n; j++） G2－＞adjmatrix[i][j]=0; while (p) { G2－＞adjmatrix[i][p－＞adjvex]=1; (3) ; } 专业word可编辑 . .. .. .. } } (1) (2) (3) 五、算法设计题（本题10分） 34.设顺序表Ｌ是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素ｘ插入到Ｌ中，使Ｌ保持有序。 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 全国2012年1月自学考试数据结构试题 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称为（ A ） A.树状结构 C.线性结构 B.网状结构 D.层次结构 2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（ D ） A.单链表 C.仅有头指针的单循环链表 B.双链表 D.仅有尾指针的单循环链表 3.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3….，pn，若p1是n，则pi是（ C ） A.i C.n-i+l B.n-i D.不确定 4.下面关于串的叙述中，正确的是（ A ） A.串是一种特殊的线性表 C.空串就是空白串 B.串中元素只能是字母 D.串的长度必须大于零 5.无向完全图G有n个结点，则它的边的总数为（ C ） A.n2 C.n(n-1)/2 B.n(n-1) D.(n-1) 6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（ B ） A.9 B.11 专业word可编辑 . .. .. .. C.15 D.不确定 7.如图所示，在下面的4个序列中，不符合．．．深度优先遍历的序列是（ A ） A.acfdeb B.aebdfc C.aedfbc D.aefdbc 8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（ D ） A.快速排序 B.归并排序 C.冒泡排序 D.直接选择排序 9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（C ） A.按层遍历 B.前序遍历 C.中序遍历 D.后序遍历 10.用ISAM和VSAM组织的文件都属于（ B ） A.散列文件 B.索引顺序文件 C.索引非顺序文件 D.多关键字文件 11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，20，7，15)，则采用的排序方法是（ C ） A.选择 B.快速 C.希尔 D.冒泡 12.当采用分块查找时，数据的组织方式为（ D ） A.数据分成若干块，每块内数据有序 B.数据分成若干块，每块中数据个数必须相同 C.数据分成若干块，每块内数据有序，块间是否有序均可 D.数据分成若干块，每块内数据不必有序，但块间必须有序 13.下述编码中不是前缀码的是（ B ） 专业word可编辑 . 9，-1，8， .. .. .. A.(00，01，10，11) C.(0，10，110，111) B.(0，1，00，11) D.(1，01，000，001) 14.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+l，则x进栈的正确操作是（ A ）指针在最大下标以上 A.top=top-1；V[top]=x C.top=top+1；V[top]=x B.V[top]=x；top=top+1 D.V[top]=x；top=top-1 15.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（ D ） A.p - > data = - 1 C.p - > next - > next=head B.p - > next = NULL D.p - > next = head 二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)请在每个空格中填上正确答案。错填、不填均无分。 16.在数据的逻辑结构和存储结构中，与计算机无关的是__逻辑结构____。 17.线性表L=(a1,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是___(n-1)/2___。 18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是___18___和___32___。 19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为___模式匹配___。 20.已知三对角矩阵A[10][10]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[6][7] 的地址为___1038___。 21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___69___。 22.有向图G如图所示，它的两个拓扑排序序列分别为__v1 v2 v3 v6 _v5 v4_ _和__v1 v3 v2 v6 v5 v4_______。 专业word可编辑 . .. .. .. 23.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为__40 38 46 56 79 84____。 24.已知广义表A=(x，((a，b)，c，))，函数head(head(tail(A)))的运算结果是__（a,b）____。 25.索引顺序文件既可以顺序存取，也可以___随机存取___。 三、解答题(本大题共4小题，每小题5分，共20分) 26.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。 初始堆： 第一趟： 第二趟： 27.设散列函数为H (key)=key ％ 11，散列地址空间为0··10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。 28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。 29.已知如图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 专业word可编辑 . .. .. .. 30.阅读下列算法，并回答下列问题： (1)简述该算法的功能； (2)写出分别输入字符串：\"abcba\"和\"abcbde\"，调用算法函数的返回值。 int symmetry(void) { int i=0,j,k；. char str[80]； SeqStack s； InitStack(&s)； gets (str)； while (str[i]!= '＼0') i++； for (j=0;jreturn 0； return 1； } (1) (2) 31.下列算法是利用二分查找方法在递减有序表R中插入元素x，并保持表R的有序性。请在空缺处填入适当的内．．容，使其成为一个完整的算法。 typedef struct { KeyType key； 专业word可编辑 . .. .. .. InfoTyep otherinfo； } RecType； typedef RecType SeqList [Maxlen] void BinInsert(SeqList R,int *n，RecType x) { int low=1，high=*n； int mid，i; while (low<=high) { mid=(low+high)/2； if (x.key>R[mid].key) (1) ； else (2) ； } for (i=*n；i>=low；i--) R[i+1]=R[i]； (3) ； ++(*n)； } (1) (2) (3) 32.阅读下列算法，并回答下列问题： (1)简述该算法中标号s1所指示的循环语句的功能； (2)简述该算法中标号s2所指示的循环语句的功能。 LinkList Insertmnode(LinkList head，char x，int m) { LinkNode*p，*q，*s; 专业word可编辑 . .. .. .. int i; char ch； p=head->next； s1：while (p&&p->data!=x) p=p->next； if (p==NULL)printf(\"error\\n\")； else { q=p->next； s2： for(i=1；i<=m；i++) { s=(LinkNode *) malloc(sizeof(LinkNode))； scanf(\"％c\"，&ch)； s->data=ch； p->next=s； p=s； } p->next=q； } return head； } (1) (2) 33.阅读下列算法，并回答下列问题： (1)该算法采用的是何种排序方法? (2)算法中的R[n+1]的作用是什么? typedef struct { 专业word可编辑 . .. .. .. KeyType key； InfoType otherinfo； }RecType； typedef RecType SeqList[MaxLen]； void sort(SeqList R，int n) { //n for (k=n-1;k>=1;k--) if (R[k].key>R[k+l].key) { R[n+1]=R[k]； for (i=k+1；R[i].key 34.假设以单链表表示线性表，单链表的类型定义如下： typedef struct node { DataType data； Struct node *next； } LinkNode，* LinkList； 专业word可编辑 . .. .. .. 编写算法，在一个头指针为head且带头结点的单链表中，删除所有结点数据域值为x的结点。函数原型为：LinkList delnode (LinkList head，DataType x) 专业word可编辑 . .. .. .. 全国2012年10月自学考试数据结构试题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 1．一个算法的时间耗费的数量级称为该算法的 专业word可编辑 . .. .. .. A．效率 C．可实现性 2．顺序表便于 A．插入结点 C．按值查找结点 B．难度 D．时间复杂度 B．删除结点 D．按序号查找结点 3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p->next->next==head C．p->next->next==NULL B．p->next==head D．p->next==NULL 4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A．(rear-front+m)％m C．(front-rear+m)％m 5．下列关于顺序栈的叙述中，正确的是 A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空 D．入栈操作不需要判断栈满，出栈操作不需要判断栈空 6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为 A．25 C．33 7．树的后序遍历等价于该树对应二叉树的 A．层次遍历 C．中序遍历 8．使用二叉线索树的目的是便于 B．前序遍历 D．后序遍历 B．26 D．34 B．rear-front+1 D．(rear-front)％m 专业word可编辑 . .. .. .. A．二叉树中结点的插入与删除 C．确定二叉树的高度 B．在二叉树中查找双亲 D．查找一个结点的前趋和后继 9．设无向图的顶点个数为n，则该图边的数目最多为 A．n-l C．n(n+1)／2 10．可进行拓扑排序的图只能是 A．有向图 C．有向无环图 11．下列排序方法中稳定的是 A．直接插入排序 C．堆排序 12．下列序列不为堆的是 ．． A．75,45,65,30,15,25 C．75,65,30,l5,25,45 B．75,65,45,30,25,15 D．75,45,65,25,30,15 B．直接选择排序 D．快速排序 B．无向图 D．无向连通图 B．n(n-1)／2 D．n2 13．对线性表进行二分查找时，要求线性表必须是 A．顺序存储 C．顺序存储且按关键字有序 B．链式存储 D．链式存储且按关键字有序 14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 ．． 的序列是 A．(4,1,2,3,5) C．(4,5,2,1,3) B．(4,2,3,l,5) D．(4,2,1,5,3) 15．下列关于m阶B树的叙述中，错误的是 ．． A．每个结点至多有m个关键字 B．每个结点至多有m棵子树 C．插入关键字时，通过结点分裂使树高增加 专业word可编辑 . .. .. .. D．删除关键字时通过结点合并使树高降低 二、填空题(本大题共10小题，每小题2分，共20分) 16．数据元素之间的逻辑关系称为数据的___逻辑___结构。 17．在线性表中，表的长度定义为__数据元素的个数____。 18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到 1、3、4、2的出栈顺序，相应的S和X的操作序列为___SXSSXSXX___。 19．在二叉树中，带权路径长度最短的树称为__哈夫曼树____。 20．已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是__6____。 21．一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符＇d＇的哈夫曼编码的长度为___2___。 22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要___n-1___条边。 23．直接选择排序算法的时间复杂度是____O(n^2)__。 24．对于长度为81的表，若采用分块查找，每块的最佳长度为____9__。 25．用二叉链表保存有n个结点的二叉树，则结点中有___n+1___个空指针域。 三、解答题(本大题共4小题，每小题5分，共20分) 26．假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一 个位置，队头指针指向队头元素)，初始状态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)算法求其最小生成树，画出最小生成树的 构造过程。 专业word可编辑 . .. .. .. 28．用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问： (1)一共需要几趟归并可完成排序。 (2)写出第一趟归并后数据的排列次序。 29．一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key％11将记录 散列到散列表HT[0..12]中去，用线性探测法解决冲突。 (1)画出存入所有记录后的散列表。 (2)求在等概率情况下，查找成功的平均查找长度。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．顺序表类型定义如下： # define ListSize 100 typedef struct { int data[ListSize]； int length； }SeqList； 阅读下列算法，并回答问题： void f30(SeqList *L) { int i,j； i=0； while(i { for(j=i+1; j 专业word可编辑 . .. .. .. L->data[j-1]=L->data[j]; 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 edges[MVN][MVN]; ∥ 邻接矩阵，即边表 int n; ∥ 图的顶点数 ｝MGraph; ∥ 图类型 例如，一个有向图的邻接矩阵如下所示： 0 1 0 0 01 0 0 0 1A0 1 0 1 01 0 0 0 0 0 0 0 1 1阅读下列算法，并回答问题： Void f31(MGraph G) { Int i,j,k=0; Step1: for (i=0; i .. .. .. for (j=0; j step2: for (j=0; j (1)stepl到step2之间的二重循环语句的功能是什么? (2)step2之后的二重循环语句的功能是什么? 32．阅读下列算法，并回答问题： void f32(int r[]， int n) { Int i，j； for (i=2；i j=j-1； } r[j+l]=r[0]； 专业word可编辑 . .. .. .. } } (1)这是哪一种插入排序算法?该算法是否稳定? (2)设置r[0]的作用是什么? 33．顺序表类型定义如下： typedef int SeqList[100]； 阅读下列算法，并回答问题： void f33(SeqList r， int n) { int a, b，i； if (r[0] else { a=r[1]； b=r[0]； } for (i=2；i } (1)给出该算法的功能； (2)给出该算法的时间复杂度。 五、算法设计题(本题10分) 34．二叉树的存储结构类型定义如下 typedef struct node{ int data； struct node *lchild， *rchild； } BinNode； 专业word可编辑 . .. .. .. typedef BinNode *BinTree； 编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。 函数的原型为：void f34(BinTree T, int *count, int *count和*sum的初值为0。 * sum) 专业word可编辑 . .. .. .. 全国2013年1月自学考试数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．数据的逻辑结构可以分为 专业word可编辑 . .. .. .. A．动态结构和静态结构 C．线性结构和非线性结构 B.顺序结构和链式结构 D.简单结构和构造结构 2．线性表是一个有限序列，组成线性表的基本单位是 A．数据项 C．数据域 B.数据元素 D.字符 3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可 ．．能的出栈序列是 ．A．dcba C．cadb 4．稀疏矩阵的三元组表是 A．顺序存储结构 C．索引存储结构 B.链式存储结构 D.散列表存储结构 B.cbda D.cdba 5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是 A．5 C．7 6．下列编码集合中，属于前缀编码的一组是 A.{11,10,001,101,0001} C.{11,01,001,0101,0001} 7.如题7图所示二叉树的中序序列为 A．ACDB B．DCBA C．CDBA D．ABCD 题7图 8．有向图中所有顶点入度之和与所有顶点出度之和的比是 B.{00,010,0110,1000} D.{0,10,110,1011} B.6 D.8 专业word可编辑 . .. .. .. A．1/2 C．2 B.1 D.4 9．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是 A.e C.n2-2e 10.n个顶点的无向连通图，其生成树的边数为 A.n-l C.n+l B.n D.nlogn B.2e D.n2-e 11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为 A．2 C．4 从大到下 自底向上排序 B.3 D.5 12．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是 A.(13,44,55,26,8,29) C.(8,13,26,29,44,55) 13．采用分块查找时，要求数据 A．块内有序 C．分块无序 14.下列关于散列函数的说法正确的是 A．散列函数越复杂越好 B.散列函数越简单越好 C．用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下，散列函数越简单越好 15.下列关于m阶B树的叙述中，错误的是 ．．A．每个结点至多有m棵子树 B.每个结点至多有m-1个关键字 B.分块有序 D.每块中数据个数必须相同 B.(13,26,55,44,8,29) D.(29,26,8,44,55,13) 专业word可编辑 . .. .. .. C．所有的叶结点均在同一层上 D.根结点至少有m/2棵子树 非选择题部分 注意事项： 用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。 二、填空题（本大题共10小题，每小题2分，共20分） 16．算法的时间复杂度与实现时采用的程序设计语言____无关________。 17．在长度为n的顺序表的第i(1≤i≤n)个元素之后插入一个元素时，需向后移动______n-i_____个元素。 18．设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为___(front+1)%m________。 19．树的前序遍历序列等同于该树对应二叉树的___前序_遍历序列。 20．一个100×90的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是__66__。每个元素要用行号,列号,元素值来表示,在用三元组表示稀疏矩阵,还要三个成员来记住,矩阵的行数列数,总的元素数,所以所需的字节数是10*（1+1+1）*2+3*2=66 21．当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是_ n+1 ___。 n个节点则有2n个链域，除了根节点没有被lchild和rchild指向，其余的节点必然会被指到。所以空链域有2n-(n-1)=n+1 22．采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数为__m__。 23．对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是_____冒泡排序______。 24．在16个记录的有序顺序表中进行二分查找，最大比较次数是_____5______。 25．在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是_稳定___的。 三、解答题（本大题共4小题，每小题5分，共20分） 26．在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？ 27．画出题27图所示树的孩子链表。 专业word可编辑 . .. .. .. 题27图 28．已知一个无向图G如题28图所示，以顶点①为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。 题28图 29．判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。 ①(1,5,7,20,18,8,10,40) ②(18,9,5,8,4,17,21,6) 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．单链表类型定义如下： typedef struct node { DataType data; struct node *next; }ListNode; typedef ListNode *LinkList; 阅读下列算法，并回答问题： void f30 (LinklList head, DataType x) { ∥head是带头结点的非空单链表的头指针 ListNode *p， *q; 专业word可编辑 . .. .. .. p=head; while（p->next->next） p=p->next; q=(ListNode*) malloc (sizeof(ListNode)); q->data=x； q->next=p->next; p->next=q； } (1)该算法的功能是什么？ (2)若单链表的长度为n，算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗？ 31．阅读下列算法（假设栈的操作函数都已定义），并回答问题： void f31 ( ) { SeqStack S； char x， y； x=′c′； y=′k′； Push (＆S，x)； Push (＆S，′a′)； Push (＆S，y)； x=Pop(&S)； Push(＆S，′t′)； Push(＆S，x)； x=Pop(＆S); Push(&S，′s′)； while ( !StackEmpty(&S)) 专业word可编辑 . .. .. .. { y=Pop (＆S); putchar (y)； } putchar (x)； } (1)自底向上写出执行while语句之前栈S中的元素序列。 (2)写出该函数的最后输出结果。 32．下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。 typedef enum { Link,Thread } PointerTag; ∥ 枚举值Link和Thread分别为0和1 typedef struct node { DataType data; PointerTag ltag, rtag; Struct node *lchild, *rchild; }BinThrNode; BinThrNode*f32 (BinThrNode *p) { ∥ 在中序线索树中找结点*p的中序前趋，设p非空 BinThrNode *q； if(p->ltag==Thread) (1) ; else { q=p->lchild； while(q->rtag=Link) (2) ； return q； } 专业word可编辑 . .. .. .. } 33．分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。 void f33( int a[ ],int n ) { int i，j，k，t； for (i=0；i if (a[k] typedef struct node { int data; struct node *lchild,*rchild; }*BSTree； 编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。 函数原型为void f34（BSTree T， int m， int n） 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 全国2013年10月自学考试数据结构试题 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 专业word可编辑 . .. .. .. 1．算法的时间复杂度表征的是 A．算法的可读性 C．执行算法所耗费的时间 B．算法的难易程度 D．执行算法所耗费的存储空间 2．对需要频繁插入和删除结点的线性表，适合的存储方式是 A．顺序储存 C．索引存储 B．链式存储 D．散列存储 3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是 A．p->next->next==head C．p->next->next==NULL 4．迪杰斯特拉(Dijkstra)算法的功能是 A．求图中某顶点到其他顶点的最短路径 C．求图的最小生成树 B．求图中所有顶点之间的最短路径 D．求图的拓扑排序序列 B．p->next==head D．p->next==NULL 5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是 ．．．A．4，5，3，2，1 C．1，2，3，4，5 B．4，3，5，1，2 D．5，4，3，2，1 6．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为 A．1015 C．1028 7．深度为4的完全二叉树的结点数至少为 A．4 C．13 B．8 D．15 B．1016 D．1030 8．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中 A．结点k对应行元素之和 C．结点k对应行和列元素之和 B．结点k对应列元素之和 D．非零元素之和 专业word可编辑 . .. .. .. 9．无向图G的邻接矩阵一定是 A．对称矩阵 C．三角矩阵 B．对角矩阵 D．单位矩阵 10．下列关于有向带权图G的叙述中，错误的是 ．．A．图G的任何一棵生成树都不含有回路 B．图G生成树所含的边数等于顶点数减1 C．图G含有回路时无法得到拓扑序列 D．图G的最小生成树总是唯一的 11．在下列排序算法中，关键字比较次数与初始排列次序无关的是 A．冒泡排序 C．直接插入排序 B．希尔排序 D．直接选择排序 1 2．对下图进行拓扑排序，可以得到的拓扑序列是 A．a b c d e C．b c a d e 13．下列线性表中，能使用二分查找的是 A．顺序存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) B．b a c d e D．a b d c e B．链式存储(2,12,5,6,9,3,89,34,25) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是 A．顺序查找 C．散列查找 B．分块查找 D．基于B树的查找 15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是 A．快速排序 B．冒泡排序 专业word可编辑 . .. .. .. C．直接选择排序 D．直接插入排序 二、填空题(本大题共10小题，每小题2分，共20分) 1 6．数据的同一种逻辑结构，可以对应多种不同的_____存储结构（物理结构）_____。 17．若在长度为n的顺序表第i个元素之前插入一个元素，则需要向后移动的元素个数是_n-i+1_________。 18．顺序栈存放在S[m]中，S[0]为栈底，栈顶指针top初始值为-1，则栈满的条件是top= _____m-1_____。 19．队列只能在队尾进行插入操作，在队首进行_____删除_____操作。 20．广义表A=(x，((y，z)，a，b))，则函数head(head(tail(A)))的值是____(y，z)______。 21．以权值分别为4，3，2，1的四个叶子结点构成的哈夫曼树，其带权路径长度WPL是___19__WPL=4*1+3*2+1*3+2*3=19 22．图的遍历方法有两种，一种是深度优先遍历，另一种是____广度优先遍历______。 23．如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序____不变______。 24．己知散列表表长m=11，散列函数h(key)=key％11，表中存有三个关键字15，27，39，其余地址为空，若采用线性探查法处理冲突，则关键字为60的结点保存的地址是_____7____。 25．己知图G的邻接表如题25图所示。 从顶点v1出发进行深度优先搜索，得到的深度优先搜索序列是___v1 v4 v3 v5 v2_______． 三、解答题(本大题共4小题，每小题5分，共20分) 26．设Q[M]是有M个元素存储空间的循环队列，若front指向队首元素，rear指向队尾 元素的下一位置，请分别用C语言描述下列操作： (1)将元素x入队； (2)将队首元素出队，并保存到变量y中； (3)计算当前队列中元素个数。 专业word可编辑 . .. .. .. 27．己知带权图G=(VE)，其中V=(A，B，C，D，E)，邻接矩阵如下 (1)画出对应的图G (2)画出图G的最小生成树 28．已知一组待排记录的关键字序列为(15，11，17，59，14，35，13，17，24，84)，请给出对应的小根堆序列。 29．已知二叉树如题29图，请画出该二叉树的前序线索。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 30．阅读下列函数并回答问题 typedef struct node{ DataType data； struct node *next； }LinkNode； Typedef LinkNode*Linklist； void DeleX(Linklist head，DataType x) { LinkNode*p，*q，*s； p=head；q=p-->next； while(q!=NULL) 专业word可编辑 . .. .. .. if(q->data==x){ s=q；q=q->next； free(s)；p->next=q； } else{ p=q；q=q->next； } } (1)执行该函数后，单链表head中data值为x的结点数是多少? (2)该函数的功能是什么? 31．阅读下列函数并回答问题 typedef struct node{ DataType data； struct node *lchild， *rchild； }BinTNode； typedef B inTNode *BinTree； void Inorder(BinTree bt) { if(bt!=NULL){ Inorder(bt->lchild)； printf(〃％c〃，bt->data)； Inorder(bt->rchild)； } } 专业word可编辑 . .. .. .. (1)给出对如题3 1图所示的二叉树执行函数Inorder后得到的输出序列。 (2)该函数的功能是什么? 32．下列函数实现直接插入排序，请填写适当内容，使其功能完整。 void f32(int r[]，int N) { int i，j； for(i=2； (1) ； (2) ) { r[0]-r[i]； j=i-1； while( (3) ) { r[j+1]_=r[j]； j=j-1； } r[j+l]= r[0]； } } 33．函数BinSearch实现二分查找，请回答下列问题。 (1)在空白处填写适当内容，使函数功能完整。 (2)查找成功时函数的返回值是什么? (3)查找失败时函数的返回值是什么? 专业word可编辑 . .. .. .. int BinSearch(SeqList R，KeyType k，int n) { int low=0，mid，high=n-1； while(10w<=high){ mid= (1) ； if(R[mid].key==k) return mid； if(R[mid].key>k) high=mid-1； else low=mid+l； } return-1； } 五、算法设计题(本题10分) 34．已知： typedef struct node{ int data； struct node *next； } LinkNode； typedef LinkNode *LinkList； 请编写原型为int Listisequal(LinkList A，LinkList B)的函数，指针A、B分别指向两个带头结点的单链表。函数功能是：若单链表A、B中全部对应结点的data值相等，则返回1，否则返回0。 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 全国2014年4月自学考试数据结构试题 一、单项选择题（本大题共15小题，每小题2分，共30分） 专业word可编辑 . .. .. .. 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关的概念是 ．．A.栈 C.顺序表 B.链表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 C.1018 B.1016 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 C.4 4.下列关于队列的叙述中,错误的是 ．．A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 C.便于输入输出 6.一棵二叉树的第7层上最多含有的结点数为 A.14 C.127 7.下列选项为完全二叉树的是 A B.64 D.128 B.节省存储空间 D.降低时间复杂度 B.3 D..6 专业word可编辑 . .. .. .. 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e C. 2e B. e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 C.2 B.1 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n） C. O（n2） B. O（n+e） D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是 A.归并排序 C.直接选择排序 B.快速排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 C.直接插入排序 B.冒泡排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 C.顺序查找 14.下列关于m阶B树的叙述中,错误的是 ．．A.根结点至多有m棵子树 B.所有叶子都在同一层次上 C.每个非根内部结点至少有 棵子树 B.二分查找 D.折半查找 D.结点内部的关键字可以是无序的 专业word可编辑 . .. .. .. 15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是 A.线性探查法 C.双重散列法 B.二次探查法 D.拉链法 二、填空题（本大题共10小题,每小题2分,共20分） 16.数据结构研究的内容包括数据的逻辑结构、__存储结构______和数据的运算。 17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是___ L->prior==L _____。 18.普里姆（Prim）算法完成的功能是求图的_____最小生成树___。 19.若三维数组a［4］［5］［6］的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是___ 338 _____。 20.二叉树的线索链表利用____空指针域____存放遍历时得到的前趋或后继结点的指针。 21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为___n*n_____。 22.若无向图中任意两个不同的顶点间都有路径,则称该图为___连通图_____。 23.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是___快速排序_____。 24.假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是_m(m+1)/2_______。 25.顺序查找算法的平均时间复杂度为_____O(n)___。 三、解答题（本大题共4小题,每小题5分,共20分） 26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串\"a*b-c\"改变为\"ab*c-\"的操作步骤。例如：将\"ABC\"改变为\"BCA\则其操作步骤为XXSXSS。 XSXXSSXXSS 27.假定电文字符集为{A,B,C,D,E,F,G,H},它们在电文中出现的次数分别为{19,6,12,5,38,3,13,4）,为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。 哈夫曼编码： 专业word可编辑 . .. .. .. A：111 C：100 E：0 G：101 B：11011 D：11010 F：11000 H：11001 28.设图以邻接表存储,如题28图所示。 （1）写出从顶点v1出发图的深度优先搜索遍历序列。V1→V2→V5→V3→V4→V6 （2）写出从顶点v1出发图的广度优先搜索遍历序列。V1→V2→V3→V4→V5→V6 29.（1）一个排序方法稳定的含义是什么？ （2）快速排序是稳定的吗？举例说明。 解：1> 如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的； 2> 快速排序是不稳定的，例如序列[2,2,1] 四、算法阅读题（本大题共4小题,每小题5分,共20分） 30.阅读下列算法,并回答问题： void f30（SeqStack S） { int k=0； CirQueue Q； SeqStack T； InitQueue（&Q）； //初始化队列Q InitStack（&T）； //初始化栈T while （!StackEmpty（&S）） 专业word可编辑 . .. .. .. { k++; if （k%2!=0） Push（&T, Pop（&S））; else EnQueue（&Q, Pop（&S））; } //第一个循环 while （!QueueEmpty（&Q）） //第二个循环 Push（&S, DeQueue（&Q））; while（!StackEmpty（&T）） //第三个循环 Push（&S,Pop（&T））； } 设栈S=（1,2,3,4,5,6,7）,其中7为栈顶元素。调用函数f30（S）后, （1）第一个循环结束后,栈T和队列Q中的内容各是什么？ （2）第三个循环语句结束后,栈S中的内容是什么？ 解：1>第一个循环结束后T与Q内容为 T：7 ,5,3,1 Q：6,4,2 2>第三个循环结束后栈S的内容为 S：6,4,2,1,3,5,7（7为栈顶元素） 31.二叉树的二叉链表类型定义如下： typedef struct node { DataType data； struct node *lchild, *rchild; } BinNode; typedef BinNode *BinTree； 阅读下列算法,并回答问题： void f31（BinTree BT） { BinNode *s; 专业word可编辑 . .. .. .. if （BT） { s=BT->lchild； BT->lchild=BT->rchild; BT->rchild=s； f31（BT->lchild）； f31（BT->rchild）； } } （1）该算法的功能是什么？ （2）以下算法功能是否等价于上面的算法？ void f3la（BinTree BT） { BinNode *s; if（BT） { f31a（BT->lchild）； f31a（BT->rchild）； s=BT->lchild; BT->lchild=BT->rchild; BT->rchild=s； } } 解：1> 交换二叉树BT所有结点的左右子树交换 2> 功能等价 32.单链表类型定义如下： 专业word可编辑 . .. .. .. typedef struct node { int data; struct node *next; } ListNode; typedef ListNode *LinkList; 用不带头结点的单链表存储待排数据,链表头指针为head。下列直接选择排序算法对链表按升序进行排序,请在答题纸相应位置填写适当内容使算法完整。 void f32（LinkList head） { ListNode *p, *q, *r; int tmp; p=head; while（p） { q=p； r=->next; while（ (1) ） { if（ (2) ） q=r； r=r->next; } tmp=q->data; q->data=p->data; p->data=tmp; p= (3) ； } } 解：1> r！=NULL 专业word可编辑 . .. .. .. 2> r->data < q->data 3> p->next 33.实现二分查找的递归章法如下,在答题纸相应位置填写适当的内容使算法完整。 typedef struct{ KeyType key; InfoType otherinfo; }NodeType; typedef NodeType SeqList［n+l］; int f33（SeqList R, int low, int high, { int mid; if（low>high） return 0； mid= （1） ； if（R［mid］.key==K） return （2） ； if（R［mid］.key (3) ； } 解：(1) (low+high)/2 (2) mid (3) f33(R,low,mid-1,K) 五、算法设计题（本题10分） 34.单链表类型定义如下： 专业word可编辑 KeyType K） . .. .. .. typedef struct node { int data; struct node *next; } ListNode; typedef ListNode *LinkList; 设计算法在带头结点的单链表L中删除数据值最小的结点（设链表中各结点数据值 均不相同）。函数的原型为：void f34（LinkList L） 解：void f34(LinkList L) { ListNode *p,*pre; If(!L->next)return; Pre=L;p=L->next; While(p->next){ If(p->next->data P=pre->next; Pre->next=p->next; Free(p); } 全国2014年10月自考考试数据结构试题 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 全国2015年10月自学考试数据结构试题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 1．下列选项中，不属于线性结构的是 A．网 B．栈 C．队列 D．线性表 2．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为 A．n—i B．n—i—l C．i D．i+1 3．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 4．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是 A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先 连续存放，则元素a[8][5]的起始地址是 A．SA+141 B．SA+144 C．SA+222 D．SA+255 6．广义表A=(x，((y)，((a))，A))的深度是 A．2 B．3 C．4 D．∞ 7．一棵左子树为空的二叉树在前序线索化后，其空指针域个数为 A．0 B．1 C．2 D．不确定 8．下列关于哈夫曼树的叙述中，错误的是 A．用n个结点构造的哈夫曼树是唯一的 B．哈夫曼树中只有度为0或度为2的结点 专业word可编辑 . .. .. .. C．树中两个权值最小的结点可能是兄弟结点 D．同一结点集构造的二叉树中，哈夫曼树的WPL最小 9．6个顶点的强连通图中，含有的边数至少是 A．4 B．5 C．6 D．7 10．对题l0图进行深度优先搜索遍历，下列选项中，正确的遍历序列是B 11B 12．有向图采用邻接矩阵存储，某一行中非零元素的个数等于 A．对应顶点v的度 B．对应顶点v的出度 C．对应顶点v的入度 D．依附于对应顶点v的边数 13．下列选项中，符合堆定义的是 A．{102，24，55，60，89，93} B．{24，89，55，60，93，102} C．{102，93，55，60，89，24} D．{102，60。89，93，55，24} 14．已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为 A．{25，51，66，82，98，108} B．{25，51，66，98，82，108} 专业word可编辑 . .. .. .. C．{51，25，66，108，98，82} D．{51，25，66，82，98，108} 15．下列选项中，其平均查找性能与基于二叉排序树的查找相当的是 A．二分查找 B．顺序查找 C．分块查找 D．索引顺序查找 二、填空题 (本大题共l0小题，每小题2分，共20分) 16．线性表(a1，a2，…，an)中，除____ a1___外，每个元素都有唯一的直接前趋。 17．指针P指向单链表中某个结点，在P所指结点后插入指针s所指的结点，正确的操作序 列是___s->next=p->next; p->next=s____。 18．设Push，、Pop分别表示人栈和出栈操作，x=10，y=20，z=30。依次进行下列操作： Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分别是____30,30___。 19．广义表L=(a，(b，e，(e，f，g，h)))，head(L)= __a_____。 20．设树T的度为3，其中度为1、2和3的结点个数分别为3、2和1，则T中叶子结点的个数为___5____。 21．由一棵二叉树的后序遍历序列和___中序____遍历序列可以唯一确定该二叉树。 22．在有n个顶点的无向图中，任一顶点的度不大于__n-1_____。 23．借助于一个栈来实现的图的遍历算法是__深度优先搜索遍历_____。 24. 若有向图中存在拓扑排序序列，则该图一定不存在____回路___。 25．已知关键字序列为{66，82，25，51，98，108}，一趟二路归并排序的结果为 __66，82，25，51，98，108_____。 三、简答题(本大题共4小题，每小题5分。共20分) 26．已知n阶对称矩阵A的元素为ai,j(0≤i，j≤n一1)，采用“按行优先”将下三角部分的元素(含主对角线)保存在一维数组sa中，且约定元素a0,0保存在sa[0]中，元素ai,j (≤i，j≤n-1)保存在sa[k]中，请给出由下标i，j计算下标k的计算公式。 27.己知二又树T如题27图所示。 专业word可编辑 . .. .. .. 请问答下列问题： (1)画出该二叉树对应的森林。 (2)写出对森林进行前序遍历的遍历序列i 28．题28图所示为一棵含2个关键字的3阶B树T。现将关键字序列{40，60，70，20，10}依次插入到T中，画出每插入一个关键字后得到的树型。 29．给定无向带权连通图G如题29图所示，从顶点v0开始，使用普里姆(Prim)算法，求G 的最小生成树T。请回答下列问题。 (1)画出最小生成树T。 (2)计算T中各边权值之和。 四、算法阅读题(本大题共4小题，每小题5分，共20分) 专业word可编辑 . .. .. .. 30．请写出下列程序段的输出结果。 专业word可编辑 . .. .. .. 31．己知存储稀疏矩阵三元组表的类型定义如下： 专业word可编辑 . .. .. .. 32．已知二叉树的二叉链表类型定义如下： 为完成指定功能，请在空白处填写适当内容，使其功能完整。 33．函数f33的参数t指向题33图所示的二叉排序树的根，阅读程序，回答下列问题。 专业word可编辑 . .. .. .. (1)若连续3次调用函数f33，参数K的值依次取10、25、10，写出每次调用后函数的输 出结果； (2)说明函数f33的功能。 五、算法设计题(本大题共l小题。共l0分) 34．已知顺序表SeqList定义如下： typedef struct{ KeyType key； InfoType otherinf0； }RecType： typedef RecType SeqList[MAXSIZE+1]； 编写函数，用冒泡排序法将n个元素的待排序列R按关键字降序排序。函数原型为： int f34(SeqList R，int n)。 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . .. .. .. 专业word可编辑 . 因篇幅问题不能全部显示，请点此查看更多更全内容