上饶师范学院模拟试题一

PAGEPAGE1上饶师范学院模拟试题一课程名称：数据结构适用学期：第四学期适用专业：计算机科学与技术适用层次：本科班级：学号：姓名题号一二三四五六七总分得分得分一．选择题(每小题2分，10小题共20分)1．在数据结构中，从逻辑结构上可以把数据结构分成。A．紧凑结构和非紧凑结构B．线性结构和非线性结构C．动态结构和静态结构D．内部结构和外部结构2．用链表表示线性表的优点是。A．便于随机存储B．花费的存储空间较顺序存储少C．便于插入和删除操作D．数据元素的物理顺序与逻辑顺序相同3．已知两个串为s1=“bccadcabcadf”，s2=“abc”，则s2在s1中的起始位置是。A．9B．8C．7D．64．若进栈序列为1，2，3，4，进栈过程中可以出栈，则不可能是一个出栈序列。A．1，4，3，2B．2，3，4，1C．3，1，4，2D．3，4，2，15．对图(1)中的二叉树,按先序遍历得到的结点序列为。AA．ABCDHEIFGB．ABDHIECFGBCC．HDIBEAFCGD．HIDBEFGACDEFGHI图(1)6．如下图所示的4棵二叉树中，不是完全二叉树。A．B．C．D．7．进行二分法检索，则线性表。A．必须以顺序方式存储B．必须以链式方式存储，且数据元素按值排好序C．必须以链式方式存储D．必须以顺序方式存储,且数据元素按值排好序8．一组记录的排序码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。A．38，40，46，56，79，84B．40，38，46，79，56，84C．40，38，46，56，78，84D．40，38，46，84，56，799．选择排序和归并排序的稳定性分别是。A．都稳定B．稳定、不稳定C．不稳定、稳定D．都不稳定10．对如下无向图2，若从顶点V1开始，按深度优先搜索法进行遍历，则可能访问顺序为。A．B．C．D．V1V2V3V4V5V6V7V8图2得分二．填空题(每小题2分，8小题共16分)11．数据的存储结构基本上可分为、。12．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行操规作。13．设a=‘aBc2*1XY+lq456XY’，则Length(a)为,SubStr(a,7,3)为。14．队列是限制插入只能在表的一端、而删除在表的另一端进行的线性表，其特点是。15．用顺序方法将完全二叉树的结点逐层存放在数组A[1．．n]中，结点A[i]若有左孩子，则该左孩子结点为，结点A[i]若有右孩子，则该右孩子结点为。16．顺序检索的平均检索长度是。17．在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。18．在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。得分三．概念简答题(每小题3分，3小题共9分)19．试写出在链接表示方法下，栈的基本运算。20．在所学的排序算法中，试分别给出时间复杂度是和排序算法。21．什么是树?给出树的四种表示形式。得分四．简单解答题(每小题5分，4小题共20分)22．二叉树结点采用顺序存储结构，如下图所示。1234567891011121314151617181920eafdgcjhib(1)．画出该二叉树；(2)．写出该二叉树的前序遍历、中序遍历和后序遍历结果。(5分)23．设线性表的关键字集合Key={32,13,49,55,22,39,20},选用散列函数的方法为“除余法”，解决冲突的方法为“线性探查法”，请按上述条件求出Key中各值的地址。(5分)24．给出如图(3)所示无向图G(该题把图3看成是无权图)的邻接矩阵和邻接表两种存储结构。(5分)A3B511C43D222E3F图(3)25．对上题用图示法画出Prim算法构造该网络的最小生成树步骤。(5分)得分五．程序阅读理解填空题(4小题，共5+6+6=17分)26．[程序说明]：以下程序是将一个头结点指针为a的单链表A分解成两个单链表A和B，其中结点指针分别为a和b，使得Ａ链表中含有原链表Ａ中序号为奇数的结点，而Ｂ链表中含有原链表Ａ中序号为偶数的结点，且保持原来的相对顺序，请填空使程序完成其功能。(第一空1分，其余每空2分，共5分)voiddisa(a,b)LinkList*a，*b；{LinkList*p，*q，*r；p=a；b=a->link；r=b；while(p!=NULL&&p->link!=NULL){①；②；③；r=q；p=p->link；}r->link=NULL；}27．[程序说明]：以下程序是二分法插入排序算法，请填空使程序完整。(每空2分，共6分)voidbinSort(SordObject*pvector){inti,j,left,mid,right；RecordNodetemp;for(i=1；i<pvector->n；i++){①；left=0；right=i-1；while(left<=right){mid=(left+right)/2；if(②)right=mid-1；elseleft=mid+1；}for(j=i-1；j=left；j++)pvector->record[j+1]=pvector->record[j]；if(left!=i)③；}}28．[程序说明]：以下程序是用二分检索算法在一个有序表中插入一个元素x，并保持表的有序性，请填空使程序完整。(每空2分，共6分)。(算法的思想是先在有序表r中用二分检索算法检索关键字值等于或小于x的结点，mid指向关键字值正好等于x的结点或low指向关键字值大于x的结点，然后采用移动法插入x结点。)bininsert(SeqDictionary*r，intx，intn){intlow=1；high=n；mid，inplace，i，find=0；while(low<=high&&!find){①；if(x<r[mid]．key)②；elseif(x>r[mid]．key)③；else{i=mid；find=1；}}if(find)inplace=mid；