《2022年数据结构C语言推荐》由会员分享,可在线阅读,更多相关《2022年数据结构C语言推荐(5页珍藏版)》请在金锄头文库上搜索。
1、数据结构( C语言)作业一一、单选题(每题 2 分,共 20 分)1、 链表不具有的特点是_A_。A.可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空问与线性表长度成正比2、假设图的顶点数=n, 边数 =e,那么当用邻接表表示图时,拓扑排序算法的时间复杂度为_B_。A. O(n2) B. O(n+e) C. O(n*e) D O(n3) 3、广义表 (f),(f) 的表尾是C 。A. f B. (f) C. (f) D. () 4、 若指针 L 指向一带头结点的循环单链表的头结点,该表为空表的条件是_D_为真值;A. !( L - link ); B. L
2、= (L - link) - link; C. L - link; D. L = L - link; 5、 采用分块查找时,若线性表中共有625 个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分为_B 个结点最佳。A. 10 B. 25 C. 6 D. 625 6、若线性表最常用的操作是存取第i 个元素及其直接前驱的值,则采用_A_存储方式节省时间。A顺序表B双链表C单循环链表D单链表7、下列排序算法中时间复杂度不受数据初始状态影响,恒为O(n2)的是 _C_。A、堆排序B、起泡排序C、直接选择排序D、快速排序8、若某链表中最常用的操作是在最后一个结点之后插入一个
3、结点和删除最后一个结点,则采用 _D_存储方式最节省运算时间(假设链表仅设有一个first 指针)。A. 单链表B. 双链表C. 单循环链表D. 带头结点的双循环链表9、 一棵左右子树均不为空的二叉树在后序线索化后(不带头结点的线索化),其空指针域数为B_。A、0 B、1 C、2 D、不确定10、某二叉树的先序序列和后序序列正好相反,则该二叉树一定是_B_的二叉树。A. 空或只有一个结点B. 高度等于其结点数(空树高度为0)C. 任一结点无左孩子D. 任一结点无右孩子二、填空作图解答题(第4 小题 6 分,其余 9 分,共 60分)1.依次插入 30,43,21,9,15,51 并由空树构成一
4、棵平衡二叉树,画出该平衡二叉树形成过程及其中序线索二叉树。30 30 30 30 43 21 43 21 43 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 5 页 - - - - - - - - - 30 30 15 43 15 43 9 21 9 21 51 2.已知广义表为((), a , (2,( c ,5,8);试画出该广义表的存储表示。3.用快速排序对下列关键字进行排序(图示), 基准元素取第一个元素。 70 33 79 67 46 24 30 40 写
5、出两趟排序的结果。第一趟排序之后: 40,33,67,46,24,307079或40 ,33,30, 67,46,247079;第二趟排序之后: 30,33,244067 , 4670, 79 或24 ,33,304046 ,6770 ,79 ; 若基准元素按“三者取中”的原则取,则两趟排序的结果是:第一趟排序之后: 40,33, 46,24,306779 ,70 或33 ,40,30,24, 466770 ,79 ;第二趟排序之后: 30,33, 24404667 ,70,79 或24 ,303340 , 4667, 70,79 ; 4.已知 9 个结点的值分别为19,请将各结点的值填入下面
6、二叉排序树中:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 5 页 - - - - - - - - - 5.如下图已知哈希表为空,哈希函数为H(Key)= Key MOD 11, 冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14,37,25, 16 之后的情况,并求等概率情况下所要求的平均查找长度。(1)线性探测再散列 0 1 2 3 4 5 6 7 8 9 10 14 37 25 16 (2)二次探测再散列 0 1 2 3 4 5 6 7 8
7、 9 10 25 14 37 16 线性探测再散列查找不成功时的平均查找长度=_21/11 _; 二次探测再散列查找成功时的平均查找长度=_6/4=3/2=1.5_ _; 6.已知一字符串bcbdebcecbdcabd ,试设计其赫夫曼编码并画出相应的赫夫曼树。a:1;b: 5;c:4;d:3;e:2;b d e d e b a c a c 7.在下面数组a 中链接存储着一个线性表,其表头“指针”为head=0,可利用空间表第一个元素的“指针” av=5:5 1 9 3 2 4 6 7 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
8、 - - 名师精心整理 - - - - - - - 第 3 页,共 5 页 - - - - - - - - - 现在依次进行如下操作:1) 在元素 56 前插入元素78;2)删除元素60;3)删除 25; 4)在元素56 后插入 66;5)在元素 66 前插入 88。请问,在进行上面操作后,av= 8 ,并将此时数组a 的内容填入下表:三、程序填空题(每空2 分,共 20 分)1.下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式,完成计算度为1 的结点个数的操作countNodes1( )。typedef struct BinNode int data;
9、 struct BinNode* leftchild, * rightchild; BinNode, *BinTree; void InitBinTree(BinTree &root) / 初始化二叉树root root=Null; void DestroyBinTree (BinTree &root) / 销毁二叉树root if (root = NULL) return; DestroyBinTree(root-leftchild); DestroyBinTree (root-rightchild); free(root); int countNodes1(BinTree &root) /
10、 计算二叉树root 中度为 1 的结点数 if ( root!=Null ) if(root- leftchild!=NULL & root- rightchild!=NULL) _ return countNodes1(root- leftchild)+countNodes(root-rightchild) _; else if (root- leftchild=NULL & root- leftchild!=NULL_) _return 1+countNodes1(root-rightchild)_; else if (root- leftchild!=NULL & root- righ
11、tchild=NULL ) _ return countNodes1(root-rightchild)+1_; return 0; a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 12 74 25 20 link 4 3 7 -1 2 8 -1 1 6 a 0 1 2 3 4 5 6 7 8 data 88 56 42 38 12 74 25 20 link 4 7 1 -1 5 2 -1 3 6 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共
12、5 页 - - - - - - - - - 2. 下面是某种线性表类的定义和实现( 仅给出了部分操作) 。函数 DE() 是用来判断线性表是否对称(即线性表,21naaa满足1iniaa,2,2,1ni) 。试在程序的每一划线部分填入一条语句或表达式 , 完成函数 DE() 。typedef struct Node int data; struct Node *next, *prev; Node, * List ; void InitList (List &L) / 初始化线性表L L = (List) malloc(sizeof(Node); L-next = L; L-prev = L;
13、void DestroyList (List &L) / 销毁线性表L Node *p, *q ; q = L-prev; while(_L!=q_) p = q; q = q-prev; free(p); free(L); bool DE(List &L) / 判断线性表L 对称否 Node *p, *q; P=L-nxt ; q = L -prev; while(p-data = q-data) if (p=q | p-next = = = =q ) return TRUE; else p=p-next ; q=q-next ; return FALSE; 学号: 10820495 姓名:张健华名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 5 页 - - - - - - - - -