《数据结构C语言二 20 14资料》由会员分享，可在线阅读，更多相关《数据结构C语言二 20 14资料（4页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C语言）作业二 一、 单选题(每题2分，共20分)1、关于串的叙述中，哪一个是不正确的？_A. 串是字符的有限序列 B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储2、一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是_。A. 0 B. 1 C. 2 D. 不确定3、循环队列A0,m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是_：A. rear -front+m; B. rear-front+1;C. (rear -front+m)%m; D. rear front-1;4、已知数
2、据表中的每个元素距其最终位置不远，则采用_排序算法最省时间。A.堆排序 B. 直接选择排序 C.快速排序 D. 插入排序5、下列关于求关键路径的说法不正确的是_。A.一个事件的最迟开始时间以该事件为尾的狐的活动最迟开始时间与该活动的持续时间的差 B. 一个事件的最早开始时间同以该事件为尾的狐的活动的最早开始时间相同 C. 求关键路径是以拓扑排序为基础的 D.关键活动一定定位于关键路径上6、在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_d_。A.O(1) B.O(n2) C.O(nlogn) D.O(n)7、下面程序段的时间复杂度是_。 i=1; while(i=n) i+
3、; A. O(n) B. O(n2) C. O(2n) D. O(log2n)8、若以1234作为双端队列的输入队列，则既不能由输入受限的双端队列得到，也不能由输出队列受限的双端队列得到的输出序列是_。A. 1234 B. 4231 C. 4132 D. 42139、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 。A.n B. (n-1)/2 C. n/2 D. (n+1)/210、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为_。A.O(n*e) B.O(n2) C.O(n+e) D.O(n3
4、)二、 填空作图解答题（第1小题6分，其余每题9分，共60分）1. 下面程序段的时间复杂度是什么？ for(i=0;in;i+)for(j=0;jm;j+) aij=i*j;2. 对给定文件（28,07,39,10,65,14,61,17,50,21）选择第一个元素28进行划分，写出其快速排序的排序过程。3. 对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。20104012 1630502 84. 由二叉树的中序序列及前序序列能唯一地建立二叉树，试问中序序列及后序序列是否也能唯一地建立一棵二叉树？不能则说明理由，若能则对中序序列DBEAFGC和后序序
5、列DEBGFCA构造二叉树。5.6. 如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式1+(2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。 运算数栈运算符栈7. 堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆 A.16,72,31,23,94,53 B.94,53,31,72,16,23C.16，53，23，94，31，72 D.16，31，23，94，53，72E.94，31，53，23，16，7
6、2 堆排序是一种 类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyed提出的 对含有n个元素的序列进行排序时，堆排序的时间复杂度是 所需要的附加结点是 。8. 求出下图中顶点A到其余个顶点的最短路径和最短路径长度。10 3ABCDHEFG20789919863127AE=10; AF=17; AB=19; AG=25; AC=26; AD=27; AH=28三、 程序填空题（每空2分，共20分）1. 下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算法在发现数据有序时能及时停止。void BubbleSort(int datalist, i
7、nt size) /要排序的数据存放在数组datalist中，元素个数=size int exchange,i,j,temp; i=1; exchange=1; while(i=i; j-) if(datalistj-1datalistj) _(3)_;_(4)_;_(5)_;_(6) _; i+; 2. 下面是仅给出了部分操作某线性表类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成相应的操作。typedef node int elem; struct node *next; node,*LinkListPtr;typedef struct LinkListPtr head,t
8、ail;LinkListPtr curr; LinkList;void InitLinkList(LinkList &L) /初始化线性表L.head = (node *)malloc(sizeof(node); if(L.head = NULL)coutInsufficient memory availablen ;exit(0); L.tail = L.head; L.curr = L.head; void insert(LinkList &L,int & item) /在表L的当前位置处插入元素item if(L.curr = NULL)coutCurrent position is n
9、ot a legal positionn;exit(0); ; node * newnode = (node *)malloc(sizeof(node); if(newnode = NULL)coutelem=item; (7) ; (8) ; if (L.tail = L.curr) L.tail = L.curr-next;void setFirst(LinkList &L) /将表的当前位置定位于第1个元素 (9) ; int currValue(LinkList &L) /将表的当前位置的元素值返回 if(!isInList(L)coutnext != NULL) & (!isEmpty(L); bool find(LinkList &L ,const int & eval) /从表的当前位置开始查找元素eval while (isInList(L) if ( (12) ) return TRUE; else (13) ; return FALSE;
