《2010-2011上期末试卷数据结构》由会员分享，可在线阅读，更多相关《2010-2011上期末试卷数据结构（25页珍藏版）》请在金锄头文库上搜索。
1、装订线学 院： 专 业： 学 号： 姓 名： 教学班号： 线封密云南农业大学20102011学年 上学期期末考试 数据结构 试卷（A卷）（课程代码 3111003 ）本试题满分100分，考试时间120分钟。题 号一二三四五六七八总分得 分阅卷人一选择题。（每小题2分，共40分）1组成数据的基本单位是（ ）。(A) 数据项(B) 数据类型 (C) 数据元素 (D) 数据变量2设数据结构A=(D，R)，其中D=1，2，3，4，R=r，r=，则数据结构A是（ ）。(A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合3数组的逻辑结构不同于下列（ ）的逻辑结构。(A) 线性表(B) 栈 (
2、C) 队列(D) 树4二叉树中第i(i1)层上的结点数最多有（ ）个。(A) 2i(B) 2i(C) 2i-1(D) 2i-15设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。(A) p-next=p-next-next(B) p=p-next(C) p=p-next-next(D) p-next=p6设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。(A) 6(B) 4(C) 3(D) 2第1页（共 7 页） / 7将1
3、0阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。(A) 100(B) 40(C) 55(D) 808设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）。(A) 3(B) 4(C) 5(D) 19根据二叉树的定义可知二叉树共有（ ）种不同的形态。(A) 4(B) 5(C) 6(D) 710. 设有以下四种排序方法，则（ ）的空间复杂度最大。(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序11下面关于线性表的叙述错误的是（ ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表
4、采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现12设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m13设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R+M)M14设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。(A) BAD
5、C(B) BCDA(C) CDAB(D) CBDA15设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-116设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。(A) 9(B) 10(C) 11(D) 12第2页（共 7 页）17设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。(A) n-1(B) n(C) n+1(D) 2n-118设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。(A) 2，3，5，8，6(B) 3，2，5，
6、8，6(C) 3，2，5，6，8(D) 2，3，6，5，819设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。(A) 15，25，35，50，20，40，80，85，36，70(B) 15，25，35，50，80，20，85，40，70，36(C) 15，25，35，50，80，85，20，36，40，70(D) 15，25，35，50，80，20，36，40，70，8520下面程序的时间复杂为（ ）for（i=1，s=0； i=n； i+） t=1；fo
7、r(j=1；jnext) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。2.阅读以下二叉树操作算法，指出该算法的功能。Template void BinTree ：unknown (BinTreeNode*t) BinTreeNode *p =t, *temp; if (p!=NULL) temp = pleftchild;
8、pleftchild = prightchild; prightchild = temp; unknown(pleftchild); undnown(prightchild); 该算法的功能是：_四算法、设计题。（每题题10分，共30分）。1.写出选择法排序的算法或程序。（5分）2. 设计在单链表中删除值相同的多余结点的算法。（10分）3. 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，.试写出这棵二叉树的后序遍历结果；并生成此二叉树；利用生成的二叉树对1001011001010110加密，写出密文。（15分）第4页（共 7 页）云南农业大学201
9、02011学年 上学期期末考试 数据结构 试卷（A卷）（课程代码 3111003 ）答题卡班级： 学号： 姓名： 题 号一二三四总分得 分阅卷人一选择题。（每小题2分，共40分）12345678910CCDCACCBBB11121314151617181920DBCAACBCAB二填空题。（每空1分，共15分）。12正确性 易读性 强壮性高效率有序34ABDECFDBEAFCDEBFCA顺序存储结构链式存储结567116数据项O(n2)O(nlog2n)三阅读算法题（第1题10分，第2题5分，共15分）。1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线
10、性表为（a2,a3,an,a1） 2.交换二叉树的左右子树的算法第5页（共 7 页）四算法、设计题。（每题10分，共30分）。1.FOR I=1 TO N-1FOR J= I+1 TO N IF A(I)A(J) T=A(I)A(I)=A(J)A(J)=T END IFNEXT JNEXT I3.后续遍历为：EDCBIHJGFA加密后密文为：343743572四算法、设计题。（共30分）。1. 写出冒泡法排序的算法或程序。（5分）2.设有两个有序集合A和B，要求设计生成有序集合C=AB，其中集合A、B和C用链式存储结构表示。（10分） 3. 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，(1)写出这棵二叉树的后序遍历结果；(2)生成此二叉树；(3)利用生成的二叉树对1001011001010110加密，写出密文。（15分）1.解:void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1; rj+1=rj;rj=temp;exchange=1;if (exchange=0) return；
