数据结构导论试题练习1

《数据结构导论试题练习1》由会员分享，可在线阅读，更多相关《数据结构导论试题练习1（4页珍藏版）》请在装配图网上搜索。

1、数据结构导论试题练习2课程代码： 02142一、单项选择题(本大题共15 小题，每小题2 分，共 30 分 )在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1下列描述中正确的是()A. 数据元素是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的2归并排序的时间复杂度是()A O（ n2）B.O（ nlog 2n）C.O（ n）D.O（ log2 n）3二分查找的时间复杂度是()A O（ n2）B.O（ nlog 2n）

2、C.O（ n）D.O（ log2 n）4顺序存储的表中有90000 个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同， 且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为()A 25000B.30000C.45000D.900005散列文件是一种 ()A 顺序文件B.索引文件C.链接文件D.计算寻址文件6两个矩阵 A ：m n， B： n p 相乘，其时间复杂度为 ()A O(n)B.O(mnp)C.O(n 2)D.O（ mp）7.常用于函数调用的数据结构是 ()A. 栈B.队列C.链表D.数组8二维数组A n m以列优先顺序存储，数组A 中每个元素占用1 个字

3、节，A 1 1为首元素，其地址为0，则元素A i j的地址为()A. （ i-1） m+(j-1)B.(j-1) n+(i-1)C.(j-1) n+iD.j n+i9.图的广度优先搜索使用的数据结构是()A 队列B.树C.栈D.集合10序列（21,19,37,5,2 ）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为()A (19， 21， 37， 5， 2)B.(21， 19， 5， 37， 2)C.(21， 19， 37， 2，5)D.(2， 21，19， 37，5)11数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为()A 索引存储方法B.顺序存

4、储方法C.链式存储方法D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的()A 直接前趋B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为()AO（1）B.O（ log2n）C.O（ n）D.O（ n2）14在链队列中执行入队操作，()A 需判别队是否空B.需判别队是否满C.限制在链表头p 进行D.限制在链表尾p 进行15一整数序列26， 59， 77， 31， 51， 11， 19， 42，以二路归并排序从小到大排序，第一阶段的归并结果为 ()A.31 ， 51， 11， 42，

5、 26， 77， 59， 19B.26， 59， 31， 77， 11， 51， 19， 42C.11， 19， 26， 31， 42， 59， 51， 77D.26， 11， 19， 31， 51， 59， 77， 42二、填空题 (本大题共13 小题，每小题2 分，共 26 分)请在每小题的空格中填上正确答案。错填、不填均无分。16下列程序段的时间复杂度为_。i=0 ； s=0；while （ snext=top和 _操作。23有m 个叶结点的哈夫曼树所具有的结点数为_。24在一棵具有n 个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i 的结

6、点有右孩子，那么其右孩子的编号为_。25在一棵树中，_结点没有前驱结点。26一个具有n 个顶点的有向完全图的弧数是_。27 n 个顶点的无向图G 用邻接矩阵A nn存储，其中第i 列的所有元素之和等于顶点 V i 的 _。28选择排序的平均时间复杂度为_。三、应用题 (本大题共5 小题，每小题6 分，共 30 分)29在栈的输入端元素的输入顺序为 1， 2，3， 4， 5， 6，进栈过程中可以退栈，则退栈时能否排成序列 3，2， 5，6， 4， 1 和 1， 5，4， 6，2， 3，若能，写出进栈、退栈过程，若不能，简述理由。 （用 push（ x）表示 x 进栈， pop(x) 表示 x 退

7、栈）30已知一棵二叉树的中根遍历序列为CBEDFAGH ，后根遍历序列为CEFDBHGA ，画出该二叉树。31给定表（ 15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。32如题 32 图所示无向图，（ 1）写出其邻接矩阵； （ 2）写出三种以顶点A 为起点的深度优先搜索顶点序列。题32图33用冒泡排序法对数据序列（49， 38， 65， 97， 76， 134， 27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。四、算法设计题(本大题共2 小题，每小题7 分，共 14 分 )34.编写计算二叉树中叶子结点数目的算法。35.开散列表的类型定义如下：typedef struct tagnodekeytype key;struct tagnode*next;*pointer,node;typedef pointer openhash n ;试写出开散列表上的查找算法。