《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 页 - - - - - - - - -
