2005年江苏南京林业大学数据结构考研真题.doc-资料库

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

2005 年江苏南京林业大学数据结构考研真题一．是非题：（判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。每小题 2 分，共 20 分） 1.数据的逻辑结构独立于计算机，物理结构依赖于计算机。（） 2.线性表、栈和队列的逻辑结构完全相同。（） 3.顺序存储方式只能用于存储线性结构。（） 4.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（） 5.先根遍历树和先序遍历与该树对应的二叉树，其结果不同。（） 6.外部排序与外部设备的特性无关。（） 7.不使用递归，也可以实现二叉树的先序、中序和后序遍历。（） 8.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。（） 9. 有回路的图不能进行拓扑排序。（） 10. 二叉排序树的查找和折半查找的时间性能相同。（）二．单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）。 1.被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素之间的这种联系称为______。 A. 规则 B.集合 C.结构 D.运算 2．对于顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。插入一个元素时大约要移动表中的______个元素。 A.n/2 D.n B.(n+1)/2 C.(n-1)/2 3．线性表采用链式存储时，其地址______。 A. 必须是连续的 C. 一定是不连续的 D. 连续与否均可以 B. 部分地址必须是连续的 4．设有一个空栈，栈顶指针为 1000H（十六进制，下同，且设每个入栈元素需要 1 个单位存储空间），现有输入序列为 1，2，3，4，5，经过 PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH 后，栈顶指针是______。 A.1002H B.1003H C.1004H D.1005H 5．将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三叉树的高度是______。Ａ. 4 B．5 C．6 D．7 6．数组 A[0..5,0..6]的每个元素占 5 个字节，将其按列优先．．．．次序存储在起始地址为 1000 的内存单元中，则元素 A[5,5]的地址是______。 A． 1175 B．1180 C．1205 D．1210 7．设森林Ｆ对应的二叉树为Ｂ，Ｂ有ｍ个结点，Ｂ的根为ｐ，ｐ的右子树结点个数为ｎ，森林Ｆ中第一棵树的结点个数是______。

A．m-n B．m-n+1 C．n+1 D．条件不足，无法确定 8．有 n 个顶点的强连通图至少有______条边。 A. n+1 B. n D.n(n-1) C.n-1 9．堆是一种有用的数据结构。以下关键字序列______是一个堆。 A.16，72，31，23，94，53 C.16，53，23，94，31，72 B.94，23，31，72，16，53 D.16，23，53，31，94，72 10．关键路径是 AOV 网中______。 A.从源点到汇点的最短路径 C.最长的回路 B.从源点到汇点的最长路径 D.最短的回路 11．折半查找的时间复杂度是______。 A.O(n2) C.o(nlog2n) B.o(n) D.o(log2n) 12．具有线性结构的数据结构是______。 A.树结构 B.图结构 C.广义表 D.文件结构 13．设无向图 G 中顶点数为 n,则图 G 最多有______条边。 A.n C.n(n-1)/2 D.n(n-1) B.n-1 14．设某有向图中有 n 个顶点，e 条边，进行拓扑排序时总的时间复杂度为______。 A. o(nlog2e) C. o(elog2n) D. o(e*n) B. o(e+n) 15．不满足平衡查找树概念的是______。 A.BST 树 B.AVL 树 C.折半查找判定树 D.B+树三．填空题：（本大题共 10 小题，每小题 2 分，共 20 分） 1.分析以下程序段的时间复杂度为______(用大“O”记号表示执行时间为 n（正整数）的函数)。 x=n; y=0; While(x>=(y+1)*(y+1)) y++; 2.为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的______分别设在这片内存空间的两端，这样，只有当______时，才产生上溢。 3.一个 n*n 的对称矩阵，如果以相同的元只存储一次的原则进行压缩存储，则其压缩后的存储容量为 ______。 4.广义表（a,(b,c),d,e,((f,g),h)）的长度为______，深度为______。 5.一棵有 n(n>=1)个结点的 d 度树，若用多重链表表示，树中每个结点都有 d 个链域，则在树的 nd 个链域中，有______个是空链域，只有______个是非空链域。

6.若二叉树有 n 个结点，当执行中序遍历的递归程序时，在最坏情况下为处理递归调用所设的栈需要 ______个单元。 7.一棵有 n0 个叶子结点的哈夫曼树上，其结点总数为______。 8.对于含有 n 个顶点 e 条边的无向连通图，prim 算法适用于求______网的最小代价生成树，而 Kruskal 算法适用于求______网的最小代价生成树。 9．Dijkstra 最短路径算法从源点到其余各顶点的最短路径长度按________次序产生，设有向图如下，则当源点取顶点 1 时，从顶点 1 到 2 的最短路径长度是______。 ① 50 ② 20 10 15 45 20 ③ 15 ④ 10 ⑤ 30 35 3 ⑥ 10．冒泡排序算法不会改变具有相同排序码的记录的相对次序，故冒泡排序算法是______，对 n 个不同的元素进行冒泡排序（从小到大），在最坏情况下比较次数为______。四．解答题：（本大题共 4 小题，共 20 分） 1. 证明：在求解 n 阶汉诺塔问题中，至少应执行的 move 操作次数为 2n-1。（4 分） 2. 给出以 S=’aabcbabcaabcaaba’为目标串，T=’abcaaba’为模式串的 KMP 快速匹配过程。（6 分） 3. 已知一棵度为 m 的树中有：n1 个度为 1 的结点，n2 个度为 2 的结点，……，nm 个度为 m 的结点，计算该树中共有多少叶子结点?有多少非终端结点？（4 分） 4. 已知关键字序列为（20，30，50，60，70，80），依照此顺序建立一棵 3 阶 B-树，给出建立的过程及结果树。若删除了 50 和 60，B-树的形态如何？（6 分）五．算法补充：（本大题共 4 小题，共 30 分） 1．一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef，指数域 exp 和指针域 next。现对链表求一阶导数，链表的头指针为 ha，头结点的 exp 域为-1。 derivative(Li nkList ha) { q=ha ; pa=ha->next; whil e (___(1)___) { if (pa->exp==0 ) { ___(2)___;

___(3)___; free(pa); pa=q; else { } pa->coef=___(4)___; pa->exp = pa->exp-1; q=pa; pa=pa->next; } } } 2．判断带头结点的双向循环链表 S 是否对称相等的算法如下所示，请填空补充完整。双向循环链表的存储结构为： typedef struct DuLNod e { data; ElemType struct DuLN ode struct DuLN ode * prior; * next; }DuLNode,* DuLinkList; int funct ion(DuLinkLi st s) { DuLinkList p,q; int j=1 ; p=s->next; q=s->prior; while(p!=q&& ___(5)___) if(p->data= =q->data) { ___(6)___; ___(7)___; } else j=0; return j; } 3.采用三元组顺序存储表示，求稀疏矩阵 M 的转置矩阵 T 的快速转置算法如下，请补充完整。 #define MAXSIZE 100 typedef struct{ int i,j; ElemType e; //非零元的行下标和列下标 }Triple; typedef struct{ Triple data[MAXSIZE+ 1]; int mu,nu ,tu; //矩阵的行数、列数、非零元的个数 //非零元三元组表，data[0]未用 }TSMatrix;

Void Fast TransposeSMa rtix(TSMatri x M,TSMatrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) { fo r(col=1;col< =M.nu;col++) fo r(t=1;t<=M.t u;t++) cp ot[1]=1; fo r(col=2;col< =M.nu;col++) nu m[col]=0; ++num[ ___(8)___]; cpot[ col]= ___(9)___; fo r(p=1;p<=M.t u;p++) { q=cpot[col]; col =M.data[p].j ; T.d ata[q].i=M.d ata[p].j; T.d ata[q].j=M.d ata[p].i; T.d ata[q].e=M.d ata[p].e; ___(10)___; } } } 该算法中引入了两个辅助向量 num 和 cpot，该算法的时间复杂度为：___(11)___。 4.下面是中序线索树的遍历算法，树由头节点且由指针 thr 指向。树的结点有五个域，分别为：数据域 data，左、右孩子域 lchild，rchild 和左、右标志域 ltag，rtag，规定标志域 1 是线索，0 是指向孩子的指针。（头结点的 lchild 域指向二叉树的根结点，头结点的 rchild 域指向中序遍历时访问的最后一个结点。二叉树中序序列中的第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。） inorderthread (thr) { p=thr->lchild ; while( (1 2) ) { while( (13) ) p= (14) ; pri ntf( “ %d ” ,p->data); whi le(p->rtag== 1) { p=p-> rchild; pr intf( “ %d ” ,p->data); } p= (15) ; } }

六．算法设计：（本大题共 3 小题，共 30 分） 1.设计一个算法，求出带有头结点的线性链表中数据域值为 x 的结点序号。该序号应从链表的第一个数据结点算起，若链表中无此结点则序号为 0。（6 分） 2.用 n 个单元的一维数组构成一个循环队列，设计分别满足如下条件的算法。（8 分）（1）实现在循环队列上的入队操作。（2）实现在循环队列上的出队操作。（3）计算队列中现有元素的个数。 3.二叉树采用链式存储结构，设计一个计算一棵给定二叉树深度的递归算法。（6 分） 4.对于一棵二叉排序树，设计分别满足如下条件的算法。（10 分）（1）实现在二叉排序树上的查找操作：若找到与给定数据值相等的结点，返回该结点的指针；若未找到，返回空指针 NULL。（2）实现在二叉排序树上的插入操作：若 BST 上存在与给定数据值相等的结点，给出“It is exist！” 信息，不插入；若 BST 上不存在与给定数据值相等的结点，则插入。

资料库

2005年江苏南京林业大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料