《1316271数据结构期中考考试卷A》由会员分享，可在线阅读，更多相关《1316271数据结构期中考考试卷A（2页珍藏版）》请在金锄头文库上搜索。
1、淮 阴 工 学 院 课 程 考 试 试 卷 第 1 页 共 2 页 班级姓名学号-装-订-线- 得分统计表： 一、选择题 (每题1分，15小题，共15分) 1、在数据结构中，从逻辑上可以把数据结构分为（ ）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2、线性表是具有n个（ ）的有限序列。 A表元素 B字符 C数据元素 D数据项 3、若长度为n的线性顺序表，在其第i个位置插入一个新元素算法的时间复杂度为（ ）。 A nO B 1O CO(logn) D 2nO4、算法指的是（ ） 。 A计算机程序 B解决问题的计算方法 C排序算法 D解
2、决问题的有限运算序列 5、算法分析的两个主要方面是（ ）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6、链表不具有的特点是（ ）。 A可随机访问任一元素 B插入、删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比 7、设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续
3、都可以 9、设用链表作为栈的存储结构则退栈操作（ ）。 A.必须判别栈是否为满 B.必须判别栈是否为空 C.判别栈元素的类型 D.对栈不作任何判别 10、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。 A.edcba B.decba C.dceab D.abcde 11、在单链表中，指针p指向链表某结点，现将指针s所指结点插到p所指结点之后，则其实现语句应为（ ）。 As-next=p+1；p-next=s； Bp-next=s；s-next=p-next； Csnext=pnext；pnext=snext； Dsnext=pnext；pnext=s； 12、栈和队列的
4、共同点是（ ）。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 13、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 A. N0=N1+1 B. N0=Nl+N2 C.N0=N2+1 D.N0=2N1+l 14、将递归算法转换成对应的非递归算法时，通常需要使用（ ）。 A.栈 B.队列 C.链表 D.树 15、树最合适用来表示（ ）。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 二、填空题(每空1分，10小空，共10分) 1、数据逻辑结构
5、包括 、 、 和 四种基本结构。 2、具有3个结点的树共有 种形态。 3、在以HL为表头指针的带表头附加结点的循环单链表中，判断链表为空的条件为 。 4、设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_ _（设结点中的两个指针域分别为llink和rlink）。 5、设顺序线性表中有n个数据元素，删除第i个位置上的数据元素需要移动表中_个元素。 6、设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_。 7、深度为k的完全二叉树中最少有_个结点。 三、补充算法题(每空1分，15小空，共15分) 1、判断一个带表头结点的单链表
6、 L 是否是有序表（由小到大）的算法如下所示，请在算法中的 处填入正确的语句。 struct node Elemtype data; node *next; ; 专业：计算机科学与技术 课程名称： 数据结构 学分：4 试卷编号（A） 课程编号： 1316271 考试方式： 闭卷 考试时间： 90 分钟 拟卷人(签字)： 拟卷日期： 2013-10-23 审核人(签字)： 题号 一 二 三 四 五 六 七 八 九 十 总 分 得分 淮 阴 工 学 院 课 程 考 试 试 卷 第 2 页 共 2 页 班级姓名学号-装-订-线- int issortedlist (node * L ) node *
7、p； if(L-next=NULL) ； ； while (p-next !=NULL) if ( ) return 0； else p= p-next； ； 2、以二叉链表结构存储二叉树，结点的结构如下： lchild data rchild 其中 data 域为整数，下面算法 void change(BiTree &r)的功能是：若根结点左孩子的 data域的值大于右孩子的data域的值，则交换其左、右子树，再对左右子树作同样操作。 void change(BiTree &r) if( ) return; if( ) ; p=r-lchild; r-lchild= ; r-rchild =
8、p; ; change( ); 3、先序遍历二叉树的非递归算法如下所示，请在算法中的 处填入正确的语句。 void PreOrderUnrec(Bitree *t) Stack s; StackInit(s); Bitree *p=t; while ( | ) while (p!=NULL) /遍历左子树 visite(p-data); p=p-lchild; if ( ) /通过下一次循环中内嵌while实现右子树遍历 p=pop(s); ; 四、综合题 (每题9分，5小题，共45分) 1、线性表有两种存储结构：一是顺序表，二是链表。试问： （1）两种存储表示各有哪些主要优缺点？ （2）在什
9、么情况下用顺序表比链表好？ （3）在何种情况下选用链表较优？ 2、设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序为 E2、E4、E3、E6、E5 和 E1，则栈 S 的容量至少为多少? 3、如果用一个循环数组 q0m-1表示队列时，该队列只有一个队列头指针 front，不设队列尾指针 rear，而改置计数器 count 用以记录队列中结点的个数。（1）写出队列判空、判满的条件；（2）队列中能容纳元素的最多个数是多少？ 4、已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 5、设给定一个权值集合 W=(3，5，7，9，11，14，2)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 五、算法设计题：(2小题，共15分) 1、编写算法，将一个结点类型为 Lnode 的单链表按逆序链接，即若原单链表中存储元素的次序为a1，an-1，an，则逆序链接后变为, an，an-1，a1。（7分） 2、编写算法，判断给定字符串中的括号是否匹配,这里括号仅圆括号()。（8分）
