计算机网络技术自考试卷 2013年1月自考数据结构导论试题[2]

2013年1月自考数据结构导论试题[2]  

　　A n B n

　　C n+ D 若构造一棵具有n个结点的二叉排序树 最坏的情况下其深度不超过( )

　　A B n

　　C D n+

　　 闭散列表中由于散列到同一个地址而引起的 堆积 现象 是( )

　　A 由同义词之间发生冲突引起的

　　B 由非同义词之间发生冲突引起的

　　C 由同义词之间或非同义词之间发生冲突引起的

　　D 由散列表 溢出 引起的

　　 一个序列中有 个元素 若只想得到其中前 个最小元素 最好采用的排序方法是( )

　　A 快速排序 B 堆排序

　　C 插入排序 D 二路归并排序

　　 在排序方法中 从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较 将其放入已排序序列的正确位置上的方法 称为( )

　　A 希尔排序 B 插入排序

　　C 冒泡排序 D 快速排序得分

　　二 填空题(本大题共 小题 每小题 分 共 分)

　　请在每小题的空格中填上正确答案 错填 不填均无分

　　 数据的逻辑结构通常包括集合 线性结构 ____________和图状结构

　　 设双链表中结点的前趋指针和后继指针的域名分别为t 和r 指针s指向双链表中的一个结点(该结点既非头结点 也非尾结点) 则删除s指针所指向结点的操作为 s >tl >r =s >r ; 和 ____________

　　 对稀疏矩阵进行压缩存储的目的是节省____________

　　 在一个具有n个结点的单链表中查找值为m的某结点 若查找成功 则需平均比较的结点数为____________

　　 深度为 的满二叉树上 第 层有____________个结点

　　 对一棵有 个结点的完全二叉树按层编号 则编号为 的结点 它的左孩子的编号为____________

　　 一个具有 个顶点的无向完全图有____________条边

　　 一个有向图G中若有孤 和 则在图G的拓扑序列中 顶点Vi Vj和Vk的相对位置为____________ ，vk>，vk>，vj>

　　 在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列

　　 实现二分查找的存储结构仅限于顺序存储结构 且其中元素排列必须是____________的

　　 文件的检索有三种方式 它们是顺序存取 直接存取和____________存取

　　 在插入排序和选择排序中 若原始记录已基本有序 则较适合选用____________

　　 对n个元素的序列进行冒泡排序时 最多需进行____________趟

　　三 应用题(本大题共 小题 每小题 分 共 分)

　　 写出利用直接选择排序方法对一组关键码为( )的记录进行排序时 每趟排序的结果

　　 已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA 试画出这棵二叉树

　　 设闭散列表容量为 (散列地址空间 ) 给定表( ) 散列函数H(K)=K mod 采用线性探测法解决冲突 要求

　　( )构造散列表;

　　( )求查找数 需要比较的次数

　　 如题 图所示 在栈的输入端有 个元素 顺序为A B C D E F 能否在栈的输出端得到序列DCFEBA及EDBFCA?若能 给出栈操作的过程 若不能 简述其理由 题 图