数据结构试卷2(含答案)

数据结构期末试卷
出卷人:09 数煤(1)班 1~9 号 一、判断题(5 分) 1、线性表是一种随机存取结构-------------------------------------------------------------------( ) 2、循环链表的特点是最后一个结点的指针域为 NULL--------------------------------------( ) 3. 下列不等式是否正确: O(n)<O(nlog2n)<O(n2)<O(n3)<O(nk)<O(2n) ----------------------------------------------------( ) 4. 数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像,分别 对应两种不同的存储结构:链式存储结构和顺序存储结构---------------------------------( ) 5. 抽象数据类型不可通过固有数据类型来表现和实现--------------------------------------( ) 二、选择题(15 分) 1、对顺序存储的线性表,设其长度为 n,在任何位置上插入或删除操作都是等概率的。插 入一个元素时平均要移动表中的( )个元素。 (A) n/2 (B) (n+1)/2 (C) (n -1)/2 (D) n 2、一个栈的入栈序列是 1,2,3,4,5,则栈的不可能的输出序列是( ) A 3,5,4,2,1 B 3,2,4,5,1 C 1,2,3,4,5 D 5,4,3,1,2 3、已知广义表 LS=((a,b,c),(d,e,f)),运用 head 和 tail 函数取出 LS 中原子 e 的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 4、对稀疏矩阵进行压缩存储目的是( ) 。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复 杂度 5、假设以行序为主序存储二维数组 A=array[1..100,1..100],设每个数据元素占 2 个存储单 元,基地址为 10,则 LOC[5,5]=( ) 。 A. 808 B. 818 C. 1010 D. 1020 6.在一个具有 n 个顶点的有向图中,若所有顶点的出度之和为 s,则所有顶点的入度之和为 ( ) A.s B.s-1 C.s+1 D.n 7.若要把 n 个顶点连接为一个连通图,则至少需要( )条边 A.n B.n+1 C.n-1 D.2n 8.已知一个有向图的边集为 {<a,b>,<a,c>,<.b,d>,<.b,e>,<d,e>},则由该图产生的一种可能的拓 扑序列为( ) A.a,b,c,d,e B.a,b,d,e,b C.a,c,b,e,d D.a,c,d,b,e 9.若在线性表中采用二分查找法查找元素,该线性表应该( ) A.元素按值有序 B.采用顺序存储结构 C.元素按值有序,且采用顺序存储结构 D.元素按值有序,且采用链式存储结构 10.二分查找法要求查找表中各元素的键值必须是( )排序 A.递增或递减

B.递增 C.递减 D.无序 11.采用顺序搜索方法查找长度为 n 的顺序表时,搜索成功的平均搜索长度为( ) A.n B.n/2 C.(n-1)/2 D.(n+1)/2 12 适用于动态查找表进行高效率查找的组织结构是( ) A.有序表 B.分块有序表 C.三叉排序表 D,线性链表 13.设有序表中有 1000 个元素,则用二分查找查找元素 X 最多哦需要比较( )次 A.25 B.10 C.7 D.1 14、下列对于循环队列的说法,正确的是: ( ) A 循环队列就是队列的顺序存储方式 B 判断循环队列 Q 满的条件是:Q.rear=Q.front(即队头指针与队尾指针值相同) C 判断循环队列 Q 满的条件是:Q.rear=Q.front=0 D 循环队列的存储不要求用一组地址连续的存储单元 15、在一个链栈中,已知 s 为栈顶指针(直接指向栈顶元素结点,无头结点) ,t 为栈底指针, 直接指向栈底元素,则插入 r 结点的操作为: ( ) A t->next=r; t=r; B r->next=s; s=r; C s->next=r; s=r; D r->next=t; 三、填空题(10 分) 1、对于双向链表,在两个结点之间插入一个新结点需要修改的指针供_____个,单链表为 ________个。 2、判断队列是“空”还是“满” ,可采用 2 中处理方法:1 是另设—个_____来区别 是满还 是空:少用一个_____。 3、广义表(a ,(a ,b),d ,e ,( (i , j),k) )的长度是______,深度是______。 4、在一个具有 n 个顶点的无向完全图中,包含有______条边,在一个具有 n 个顶点的有向 完全图中,包含有______条边。 5. 快 速 排 序 在 平 均 情 况 下 的 时 间 复 杂 度 为 ________ , 在 最 坏 情 况 下 的 时 间 复 杂 度 为 ________。 四、读程序写算法(3*5 分) 1、void MergeList_L(LinkList & La, LinkList &Lb, LinkList &Lc) { pa = La->next; pb = Lb->netx; pc =Lc = Lb; while(pa && pb) { if (pa->data <= pb->data) { pc->next = pa; pc = pc->next; pc->next = pb; pa = pa->next;

} else { pc->next =pb; pc = pc->next; pb= pb->next; } }//end while pc->next = pa?pa:pb; free(La); }//end function 2、void YHT() { SeqQueue Q; InitQueue(&Q); EnterQueue(&Q,1); For(n=2;n<=N;n++) { EnterQueue(&Q,1); for(i=1;i<=n-2;i++) { DeleteQueue(&Q,&temp); printf(“%d”,temp); GetHead(Q,&x); temp=temp+x; EnterQueue(&Q,temp); } DeleteQueue(&Q,&x); printf(“%d”,x); EnterQueue(&Q,1); } } 五、程序填空(3*5 分) 1、已知不带头结点的线性链表 list,链表中结点构造为(data、link) ,其中 data 为数据 域,link 为指针域。请完成下面算法填空,要求将该链表按结点数据域的值得大小从小到 大重新链接。要求链接过程中不使用除该链表意外的任何链结点空间。 Linklist LinkListSort(linklist list) { Linklist p,r,q; P=list->next; //p 是工作指针,指向待排序的当前元素 List->next=0; While(p) { r=p->next; //r 是 p 的后继 q=list;

If((________)>(__________)) //处理待排序结点 p 比第一个元素结点小的情况 { P->next = list; List = p; } Else //查找元素值最小的结点 { while((_____)&&(_______________)) q=q->next; __________________;//将当前排序结点链入有序链表中 q->next=p; } p=r; } return p; } 2、下列算法实现求采用顺序结构存储的串 s 和串 t 的一个最长公共子串。 void maxcomstr(orderstring *s,*t;int index,length) { int i,j,k,length1,com; index=0;length=0;i=1; while(i<=s.len) { j=1; while(j<=t.len) { if(s[i]==t[j]) { k=1;length1=q;con=1; while(con) if___(1)____{ length1=length1+1;k=k+1;}else____(2)___; if(length1>length){index=i;length=length1;} ____(3)___; } else__(4)___; } ___(5)___; } } 3、Void preorder(bitree *T) { bitree *stack[m]; int top; if(T!=NULL) { top=1; stack[top]=(1);

while( (2) ) { p=stack[top]; top--; printf(“%d”,p->data); if(p->rchild!=NULL) { ( 3 ); stack[top]=p->rchild;} if( (4) ) { top++; ( 5 ) ; } } } } 六、算法实现(2*10 分) 1、已知整形数组 A,从第一个单元(即 A[1])开始存储数据,且一共存储了 n 个元素。要 求编写折半查找元素 e 的过程。当数组中存在元素 e 时,返回其下标,否则返回 0.(10 分) Int BinarySearch(int *A,int n,int e) 2、已知二叉搜索树中的结点类型用 BtreeNode 表示,被定义为: struct BtreeNode {ElemType data; BtreeNode *left, *right;}; 其中 data 为结点值域,left 和 right 分别为指向左、右孩子结点的指针域。假定具有 BtreeNode*类型的指针参数 BST 指向一棵二叉搜索树 的根结点,试根据下面的函数声明编 写一个非递归算法, 向 BST 树中插入值为 item 的结点, 若树中不存在 item 结点则进行插入 并返回 1 表示插入成功,若 树中已存在 item 结点则不插入并返回 0 表示插入失败。 七、简答题(2*5 分) 1、如图,为一有向图,按要求回答问题: (5’) 写出各顶点的入度、出度和度。 (2’) 写出该图的临接表。 (3’)

2、有一个待排序的序列含 7 个记录,这 7 个关键字分别为 23,4,15,8,19,24,15,用直接插入 法对这个序列进行排序。 七、附加题: (10 分) 冒泡排序算法是把大的元素向上移 (气泡的上浮) , 也可以把小的元素向下移 (气泡的下沉) , 请给出上浮和下沉过程交替的冒泡排序算法。

参考答案: 一、1 对 2 错,最后一个结点的指针域指向头结点 3 对 4 错 5 错 二、1、C 2、D 3、C 4、C 5、B 6、A 7、C 8、A 9、C 10、A 11、D 12、C 13、B 14、C 15、D 三、 1、 4 2 2、 标志位, 元素空间 3、 5 3 4、 n(n-1)/2,n(n-1) 5、 O(nlog2n) O(n2) 四、1、 La Lb 带有头结点,按非递减顺序排列,归并 La Lb 得到 Lc, 要求 Lc 非递减顺序 2、算法功能:打印杨辉三角的前 n 行元素 五、1、q->data p->data Q->next Q->next->data<p->data P->next=q_>next 2、 (1)i+k<=s.len&&j+k<=t.len&&s[i+k]==t[j+k] (2)con=0 (3)j+=k (4)j++ (5)i++ 3、 (1)T (2) top>0 (3) top++ (4) p->lchild!=NULL (5) stack[top]=p->lchild 六、1、Int BinarySearch(int *A,int n,int e) { int low,high,mid; low=1; high=n; 1分 while(1) { mid=(low+high)/2; 2 分 if(A[mid]==e) 1分 { return mid; 1分 } else if(A[mid]>e) 1分 { high=mid-1; 1分 } else{ low=mid+1; } 1分 if(low>high) 2分 return 0;} } 2、int Insert (BTreeNode*& BST, const ElemType& item);//向二叉搜索树插入元素 { BTreeNode* t=BST, *parent=NULL; while(t!=NULL)

{

parent=t; if(item==t-&gt;data) return 0; else if(item&lt;t-&gt;data) t=t-&gt;left; else t=t-&gt;right; } //建立值为 item,左、右指针域为空的新结点 BTreeNode* p=new BTreeNode; p-&gt;data=item; p-&gt;left=p-&gt;right=NULL; //将新结点插入到二叉搜索树中的确定位置上 if(parent==NULL) BST=p; else if(item&lt;parent-&gt;data) parent-&gt;left=p; else parent-&gt;right=p; } } 七、1、 (1)

(2)

2、 【解】如图 方括号内的数据为已排好序的记录的关键字。在这个序列中有两个记录的关 键字都为 15,为表示区别,将最后一个 15 加下划线。

附加题: void BubbleSort2( int a[ ], int n) { int i; int temp; int flag=1; int low=0; int high=n-1; while(low<high && flag) { flag=0; for(i=low;i<high;i++) { if(a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } } high--; for(i=high;i>low;i--) { if(a[i]<a[i+1]) { temp=a[i];

a[i]=a[i+1]; a[i+1]=temp; flag=1; } } low++; } }


相关文档

数据结构试题 试卷二 含答案
数据结构模拟试卷2答案
数据结构模拟试卷2
数据结构试卷及答案2套
淮阴工学院数据结构期末试卷及答案(2)
数据结构试卷2
数据结构模拟考试试卷2
数据结构联考试卷2及答案
电脑版