2012年江西理工大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.35M 资料格式：doc 举报版权申诉

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2012 年江西理工大学数据结构考研真题一、选择题（每小题 2 分共 30 分） 1.深度为 6（根的层次为 1）的二叉树至多有（）结点。 A 64 B 32 C 31 D63 2.关键路径是事件结点网络中的（） A 原点到汇点的最长路径 B.从源点到汇点 C.最长的回路 D. 最短的回路 3.对于长度为 9 的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（） A.20/9 B. 18/9 C. 25/9 D.22/9 4.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于 A.n B.n-1 C.n+l1 D.2*n 5.如果以链表作为栈的存储结构，则退栈操作时 6.对线性表进行二分查找时，要求线性表必须 7.若让元素 A、B、C、D、E 依次进栈，则出栈次序不可能出现的情况为（）. A.A、B、C、D、E B.B、C、D、E、A C.E、A、B、C、D D.E、D、C、B、A 8.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL 为（ 9.对稀疏矩阵进行压缩存储目的是（

A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度 10.下面哪一方法可以判断出一个有向图是否有环（回路）∶（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 11.下列四个序列中，哪一个是堆（） A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 12.下述哪一条是顺序存储结构的优点?（） A 存储密度大 B.插入运算方但 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 13.有 n 个叶子的哈夫曼树的结点总数为（） A.不确定 B.2n C.2n+1 D.2n-1 14. 在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是∶（） A. p->next=s;s->next=p->next; B. s-next=p->next;p->next=s; C. p->next=s;p->next=s->next; D. p-next=s->next;p->next=s; 15.二维数组 SA 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内，该数组按列存放时，元素 A【4】【7】的起始地址为（ A.SA+141 B. SA+180 C. SA+222 D. SA+225 二、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列 DBEAFGC 和后序序列 DEBGFCA 构造二叉树。假定某二叉树的前序遍历序列为 ABCDEFGHIJ，后序遍历序列为 CEFDBJIHGA，据此两个序列能否唯一确定此二叉树?若不能，试画出两样具有同样上述遍历序列的二叉树. （12 分）三、假设用于通信的电文由字符集 a，b，c，d，e，，f，g}中的字母构成。它们在电文中出现的频度分别为{0.31，0.16，0.10，0.08，0.11，，0.20，0.04}，（15 分） 1）为这 7 个字母设计哈夫曼编码;

2）对这 7 个字母进行等长编码，至少需要几位二进制数?哈夫曼编码比等长编码使电文总长压缩多少? 四、已知一个无向图如图所示，试回答以下问题∶（12 分） 1）写出该图的邻接表 2）请用克鲁斯卡尔算法生成最小生成树（画出构造过程）。五如图所示的带权有向图 G，试回答以下问题∶（15 分） 1）给出从结点 v1 出发按深度优先搜索遍历 G 所得的结点序列 2）给出 G 的一个拓扑序列 3）给出从结点 v1 到结点 v8 的关键路径。六、本程序完成将二叉树中左、右孩子交换的操作。（12 分）本程序采用非递归的方法，设立一个堆栈 stack 存放还没有转换过的结点，它的栈顶指针为 tp。交换左、右子树的算法为∶ （1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。

七.一个栈的输入序列是 A，B，C，则栈的输出序列可有多少种?一一列举出来。假如一个栈的输入序列是 1，2，3，4，5，则栈的输出序列为 4，3，5，1，2 是否可以得到?为什么?（10 分）八、.对于下列一组关键字{46，58，15，45，90，18，10，62}试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。（10 分）九、设散列函数为 H（k）=k%13，散列表的地址空间为 0 到 12，用线性探查法解决冲突，将关键字（18，22，78，205，40，16，35，104，61）依次存入该散列表中，试构造散列表，并计算在等概率下的搜索成功的平均搜索长度 ASL（搜索成功的平均搜索长度 ASLsucc 是指搜索到表中己有表项的平均探查次数。它是找到表中各个己有表项的探查次数的平均值）（10 分）十、已知 L 是无表头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点，设计算法以实现在 P 结点前插入 S 结点的功能。（12 分）十一、设计算法统计一棵二叉树中所有叶结点的数目及非叶结点的数目。（12 分）

分享到：

赞收藏

资料库

2012年江西理工大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料