《计算机考研数据结构试卷十三(练习题含答案)》由会员分享，可在线阅读，更多相关《计算机考研数据结构试卷十三(练习题含答案)（6页珍藏版）》请在金锄头文库上搜索。
1、 共 25 套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷 13一、填空题1、对于一个顺序存储的线性表，在表头插入元素的时间复杂度为_,在表尾插入元素的时间复杂度为_。2、在稀疏距阵所对应的三元组线形表中，每个三元组元素按_为主序，_为辅序的次序排列。3、中缀表达示 3+X*（2.4/5-6）所对应的后缀表达示为_。4、在一棵高度为 h 的 3 叉树中，最多含有_结点。5、分析下面算法（程序段），给出最大语句频度_ _。for (i=0;in;i+)，该算法的时间复杂度是for (j=0;jnext!=p) q=q-next;s= new Node;q-next
2、=s-next=s-data=e;/填空/填空;9、在一个单链表中删除 p 所指结点的后继结点时，应执行以下操作：q= p-next;p-next= _delete_;/填空/填空10、两个串相等的充分必要条件是_。二、 选择题1、以下数据结构中哪一个是线性结构？【】A 有向图B 队列C 线索二叉树2、在一个单链表 HL 中，若要在当前由指针 p 指向的结点后面插入一个由 q 指向D B 树的结点，则执行如下【A p=q; p-next=q;】语句序列。B p-next=q; q-next=p;D q-next=p-next; p-next=q;C p-next=q-next; p=q;3、【
3、 】不是队列的基本运算。A 在队列第 i 个元素之后插入一个元素 B 从队头删除一个元素第 1 页 共 6 页 C 判断一个队列是否为空D 读取队头元素的值4、若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p ，p ，p ，312p ，若 p =n，则 p 为【i】。B. n=in1A. iC. n-i+1】_。D. 不确定5、栈的特点是【A. 先进先出6、设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作【】，队列的特点是【B. 先进后出】。A. 连接C. 求子串B. 模式匹配D. 求串长7、二维数组 A 中，每个元素 Aij的长度为 3 个字节，行下标 i 从 0
4、 到 7 ，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内，该数组按列存放时，元素 A47的起始地址为【A. SA+141 B. SA+1808、某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是【 】。A. bdgcefha B. gdbecfha C. bdgaechf9、在一非空二叉树的中序遍历序列中，根结点的右边【】。C. SA+222D. SA+225D. gdbehfca】。A. 只有右子树上的所有结点C. 只有左子树上的部分结点B. 只有右子树上的部分结点D. 只有左子树上的所有结点10
5、、具有 6 个顶点的无向图至少应有【】条边才能确保是一个连通图。A. 5B. 6C. 7D. 8三、计算与算法应用题：1. 试列出如下图中全部可能的拓扑排序序列。1234562. 设某通信系统使用 A，B ，C，D，E，F，G，H 八个字符，他们出现的概率 w=，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）。3. 给定表（19，14，22，1，66，21，83，27，56，13，10）,请按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均长度。四、阅读下列算法，分析其作用1. 阅读下列算法，说明该算法的作用。int LinkList:sum【
6、 】 int x;NodeType *p;p=Head-next;while(p!=NULL) x+;第 2 页 共 6 页 p=p-next;return x; / pop2. 读下述算法，说明本算法完成什么功能。void Btree :inordern( bnode *p, int &n ) if ( p!=NULL) inordern( p-lch, n);if ( p-lch=NULL & p-rch=NULL) n+;inordern( p-rch, n); / inordern五、算法设计1. 试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于 key的元素值。2. 已知带
7、头结点的单链表是一个递增有序表，试写一算法，删除表中值大于 min 且小于 max 的结点（若表中有这样的结点），同时释放被删除结点的空间，这里 min 和 max 是两个给定的参数。Head79152650第 3 页 共 6 页 答案一、填空1. O(n)2. 行号3. 3 x 2.4 5 6 *O(1)列号4. (35.h-1)/2， O (n )n336. 零个字符的串， 零7. 邻接矩阵 ， 邻接表8. s, p9. q-next, q10. 两个串的长度相等且对应位置的字符相同二、选择1-5BDACB 6-10ABBDA三、计算与算法应用题：1、全部可能的拓扑排序序列为：152363
8、4、152634、156234、561234、516234、512634、5123642、1004248FB29192329DHE1581114C87G3A5第 4 页 共 6 页 7.平均长度为 4.四、阅读下列算法，分析其作用1. 该算法是求链表结点个数的算法。结果返回结点个数的总和值。2. 本算法要求二叉树中叶子结点的总数的算法。用 n 值存储叶子结点的个数。五、算法设计1、可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。具体算法实现如下：/ 文件路径名:exam4alg.h#include binary_sort_tree.h/ 二叉排序树
9、类template void InOrderHelp(BinTreeNode *r, const KeyType &key)/ 操作结果: 从大到小输出以 r 为根的二叉排序树中所有的关键字值不小于 key 的元素值if (r != NULL)/ 非空二叉排序树InOrderHelp(r-leftChild, key);if(r-data key) cout data rightChild, key);/ 遍历右子树template void InOrder(const BinarySortTree &t, const KeyType &key)/ 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于 key 的元素值InOrderHelp(t.GetRoot(), key);/ 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于 key 的元素值第 5 页 共 6 页 2、 void Link :Delnode( )NodeType *p=Head-next, *q,*r=p;while(p!=NULL&p-datanext;q=p;while( q!=NULL & p-data next;r-next=q-next;r=p-next;while(r!=q) delete p;p=r;r=r-next;delete q; / delpro第 6 页 共 6 页
