重庆理工大学算法与数据结构试卷一

《重庆理工大学算法与数据结构试卷一》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、重庆理工大学考试试卷一、单项选择(每题2分，共20分)1．一个具有n个顶点的无向完全图的边数为（）A.n(n+1)/2B.n(n+1)C.n(n-1)D.n(n-1)/22．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以3．一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A.110B.108C.100D.1204．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个

2、字符C.可以链接存储D.数据元素可以是多个字符5．顺序查找法适合于存储结构为（）的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储6．下述几种排序方法中，平均时间复杂度最小的是（）A.插入排序B.选择排序C.冒泡排序D.快速排序7.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。A.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front8.3个结点可构成（）个不同形态的二叉树

3、。A.2B.3C.4D.59．对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A.100B.12C.60D.1510．栈操作的原则是（）A.先进先出B.后进先出C.栈顶插入D.栈顶删除二、填空题（每小题1分，共10分），将正确的答案写在每小题的空格内。1.在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：s->next=p;s->prior=p->prior;p->prior=s;________________=

4、s;2．散列法存储中处理碰撞（冲突）的两类基本方法是、3.设二维数组A[-2..10,-1..20]按行优先顺序存储，每个元素占4个存储单元，A[-2,-1]的存储地址是1000,则A[5,6]的存储地址是。4.设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___________，栈为满的条件是__________________。5．设有向图的邻接矩阵为A，如果图中不存在弧VI，VJ，则A[I][J]的值为：。6.设有一个链队列，结点结构为：队尾指针为Ls（≠null），

5、则执行入队操作时，S->next=Ls->next；___________；___________。7.单链表中指针P所指结点不为尾结点的条件是___________。8.G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是图。9.串S=″Iamaworker″的长度是_____。10.按先根次序法遍历树林正好等同于按遍历对应的二叉树。115534422三、算法应用题(每小题5分,共20分)1、对上图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容

6、，以说明该算法的执行过程。顶点134UV（U，V）（2，1）（2，3）（2，4）{2}{1，3，4}代价∞42（U，V）（2，3）{2，4}{1，3}代价4（U，V）（3，1）{2，4，3}{1}代价1（U，V）{2，4，3，1}代价2、有一组关键码序列{8，9，5，3，7，2，1}，分别采用冒泡排序、快速排序、直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中选择各种排序第一趟排序的结果。冒泡排序：；快速排序：；直接选择排序：直接插入排序：；二路归并：A．{1，2，5，3，7，8，9}

7、B．{1，9，5，3，7，2，8}C．{9，8，5，3，7，2，1}D．{9，5，3，7，2，1，8}E．{8，5，3，7，2，1，9}F．{8，9，3，5，2，7，1}3、设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求查找3的比较次数。4、现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，在下面的选项中选择一个编号，说明这5个结点的哈夫曼编码。（）（1）A：1，B：001，C：010，D：011，E：000（2）A：000，B：001，C：010

8、，D：011，E：1（3）A：001，B：011，C：010，D：000，E：1（4）A：000，B：1，C：010，D：011，E：001四、算法填空和分析（每小题5分，共30分）1、设单链表存放字符串,下列算法使用栈判断该字符串是否是中心对称,如abccba即为中心对称字符串.根据题目填空完善程序.typedefstructnode{chardata；structno