2018年江西师范大学数据结构与程序设计考研真题.doc

发布时间：2023-11-16 发布人：admin 分类：说明书资料大小：0.06M 资料格式：doc 举报版权申诉

第1页 / 共5页

2018年江西师范大学数据结构与程序设计考研真题.doc.pdf-第2页.jpg

第2页 / 共5页

2018年江西师范大学数据结构与程序设计考研真题.doc.pdf-第3页.jpg

第3页 / 共5页

2018年江西师范大学数据结构与程序设计考研真题.doc.pdf-第4页.jpg

第4页 / 共5页

2018年江西师范大学数据结构与程序设计考研真题.doc.pdf-第5页.jpg

第5页 / 共5页

文本预览

2018 年江西师范大学数据结构与程序设计考研真题一、单项选择题(每小题 2 分，共 20 分) 1.在一个长度为 n 的顺序表中删除第 i 个元素(1<=i<=n)时，需要向前移动()个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 2.链表是一种采用()存储结构存储的线性表。 A.链式 B.顺序 C.星式 D.网状 3.栈是一种特殊的线性表，具有()性质。 A.先进先出 B.先进后出 C.后进后出 D.顺序进出 4.表达式 3*(4+5)-6 的后缀表达式是()。 A.3456*+- B.345+*6- C. 345*+6- D.-+*3456 5.已知顺序循环队列的存储空间为数组 A[20],且当前队列的头指针和尾指针的值分别为 8 和 4,则该当前队列的元素个数为()。 A.4 B.5 C.16 D.15 6.非空不带头结点的循环单链表 head 的尾结点(由 p 指向)满足()条件。 A.p->next==NULL B.p->next==head C.p==NULL D.p==head 7.一个具有 6 层(根结点为第 1 层)的满二叉树所包含的结点个数为()。 A.15 B.31 C.63 D.64 8.有 n 个顶点的有向强连通图最少有()条边。 A.2n B.n+1

C.n-1 D.n 9.对于哈希函数 H(key)=key%11,被称为同义词的关键字为()。 A.35 和 41 B.23 和 39 C.15 和 44 D.25 和 58 10.下面的序列中初始序列构成最小堆(小根堆)的是()。 A.10,60,20,50,30 B.70,40,36,30,10 C.18,60,50,40,20 D.10,30,20,50,40 二、填空题(每小题 2 分，共 20 分) 1.一个算法中语句频度之和为 T(n)=2n²+100n,则该算法的时间复杂度是（）。 2.编号为 1,2,3 的 3 列火车通过一个栈式的列车调度站，可能得到的不同调度结果有（）种。 3.顺序循环队列中(数组大小为 n),队头指示 front 指向队列的第 1 个元素，队尾指示 rear 指向队列最后元素的后 1 个位置。若以牺牲一个数组元素空间的方式来作为循环队列满的条件，其语句为（）。 4. 在一个带头结点的非空单链表中，在 p 所指结点之后插入 s 所指结点，则执行的语句是（） 5.设有一个 10×10 的对称矩阵 A 采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角矩阵，假设其起始元素 ao 的地址为 1,每个数据元素占 2 个字节，则 as 的地址为（） 6.对于一棵具有 n 个结点的树，该树中所有结点的度数之和为（）。 7.某二叉树的前序遍历序列为 ABDC,中序遍历序列为 BDAC,则该二叉树根结点的右孩子是（） 8.在含 100 个结点的完全二叉树中，叶子结点的个数为（） 9.已知含 10 个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度为（） 10.直接插入排序在最好情况下的时间复杂度为.（）。三、程序填空与程序分析题(每小题 6 分，共 24 分) 1.设单链表的存储定义如下： typedef int datatype; typedef struct linknode{ datatypeinfo; struct linknode *next; } node; typedef node x linklist; 函数 fun1()的功能是返回带头结点的单链表 head 中数据值最大的结点地址，请将程序补充完整。 linklist fun1( linklist head) { /* head 为带头结点单链表的头指针 */ linklist max, p ; max=head->next; p=(1); while(p){

if(p->info>max->info) (2); (3) ; return max; 2.阅读如下程序代码，并回答程序后的问题： #define MAXSIZE100 typedef int datatype; typedefstruct{ datatype a[MAXSIZE]; intsize; }sequencelist; voidfun2(sequencelist*L,inti,intj) { intt; if(ia[i]%2==0)i++; while(ia[j]%2!=0)j--; t=L->a[i]; L->a[i]=L->a[j]; L->a[j]=t; fun2(a,i+1,j- 1); (1)若顺序表 L 的数据值为{2,3,4,5,7,9,12,8,11,12},求执行 fun2(&L,0,L.size-1)以后，顺序表 L 的数据值： (2)简述函数 fun2 的功能。 3. 设二叉树的存储定义如下： typedef char datatype;/*结点属性值的类型*/ typedef struct node{/*二叉树结点的类型*/ datatypedata; struct node*lchild,*rchild; } bintnode; typedef bintnode *bintree; 函数 fun3 的功能是在二叉树 t 中查找值为 x 的结点，若找到则返回该结点的地址，否则返回 NULL。请将程序空白处补充完整。 bintree fun3(bintree t, datatype x) {bintree p; if( 1 ) )return NULL; if(t->data==x)return (2) p=fun3(t->lchild,x): if(p)returnp; elsereturn(3); 4.设顺序表的存储定义如下： #define MAXSIZE 100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int size;

}sequencelist; 函数 fun4 的功能是采用直接选择排序算法对顺序表 L 中的元素进行非降序排序。请将程序空白处补充完整。 voidfun4(sequencelist*L) {int i,j,k,t; for(i=0;isize- 1;i++){ k=i; for(j=i+1;jsize;j++) if(L->a[j]a[k]) 1) ; if( (2)){t= L->a[k];L->a[k]= L->a[i]; (3);} 四、解答题(每小题 10 分，共 40 分) 1. 已知一颗二叉树如下图所示：试求：(1)写出该二叉树分别进行中序遍历和后序遍历的遍历序列； (2)画出该二叉树对应的森林。 2. 已知一个无向网络图的顶点集为{A,B,C,D,E,F},其邻接矩阵如下所示： (1)请画出该无向网络图； (2)画出从 A 结点出发用 Prim 算法建立最小生成树的过程。 3. 假设通讯电文中只用到{ A、B、C、D、E、F}6 个字母，它们在电文中出现的相对频率分别为{ 6、2、4、1、10、9 },试为它们设计 Huffman 编码。 4. 设待排序的 10 个记录的排序码序列为 { 27,12,45,6,18,51,32,34,10,2},画出使用 shell 插入排序算法进行排序的数据状态变化过程。五、算法与程序设计题(第 1、2 题每小题 14 分，第 3 小题 18 分，共 46 分) 答题要求： ①用自然语言说明所采用算法的思想； ②用 C 语言(或其他程序设计语言)写出对应的算法程序，并加上必要的注释。 1、设单链表的存储定义同第三大题第 1 小题。设计一个算法，删除一个带头结点的单链表

中所有值为奇数值的结点。 2、设二叉树的存储定义如下： typedef int datatype;/*结点属性值的类型*/ typedef struct node{ /*二叉树结点的类型*/ · datatype data; structnode*lchild,*rchild; } bintnode; typedefbintnode*bintree; 设计一个算法，其功能是返回一棵给定二叉树在中序遍历下的第一个结点和最后一个结点。 3、设二叉树的存储定义同上一题。设计一个算法，判断一个给定的二叉树是否为二叉排序树，设此二叉树中结点的数据值互不相同。

分享到：

赞收藏

资料库

2018年江西师范大学数据结构与程序设计考研真题.doc

相关推荐

考研

热门标签

最新资料