2022年数据结构笔试题答案.docx

《2022年数据结构笔试题答案.docx》由会员分享，可在线阅读，更多相关《2022年数据结构笔试题答案.docx（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构笔试题答案一、挑选题1. C 插入排序从后面插入的时候,操作；只要把 8 和 9 交换一下就行了, 遍历到前面都不再有任何冒泡排序第一次循环把 9 沉到最终面,然后其次次循环发觉没有任何交换操作,说明已经排好序了；2. A 3. D 已知前序和后序不能唯独确定4. B 5. D 二、填空题1.2.1.=null 2p-next 3r.=null 4r-data data 5r-next 6p-next 题中 p 指向无序区第一个记录,q 指向最小值结点,一趟排序终止,p 和 q 所指结点值交换,同时向后移p 指

2、针；EACBDGF 3.sort_b_tree&*tree-right,s sort_b_tree&*tree-left,s 三、简答题1. 数组和链表的区分,请具体说明；从规律结构来看：a数组必需事先定义固定的长度（元素个数）,不能适应数据动态地增减的情形；当数据增加时,可能超出原先定义的元素个数；可以依据下标直接存取；当数据削减时, 造成内存铺张；数组b 链表动态地进行储备安排,可以适应数据动态地增减的情形,且可以便利地插入、删除数据项；（数组中插入、删除数据项时,需要移动其它数据项,特别繁琐）链表必需依据 next 指针找到下一个元素从内存储备来看：名师归纳总结 a静态 数组从栈中安排空

3、间, 对于程序员便利快速,但是自由度小第 1 页,共 49 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆b链表从堆中安排空间, 自由度大但是申请治理比较麻烦从上面的比较可以看出,假如需要快速拜访数据,很少或不插入和删除元素,就应当用数组；相反,假如需要常常插入和删除元素就需要用链表数据结构了；2. 排序算法有哪些？ 排序算法有许多,每种算法有不同的时间和空间复杂度,效率也有差别, 那么针对使用上也有不同的场合；原就上说, 数据结构是一门领域,跟语言没有确定的联系,许多时候同样的算法可以用许多种语言实现；下面列一些常见的算法：插入排序,

4、冒泡排序,挑选排序,快速排序,堆排序,归并排序,基数排序,希尔排序等；3. 怎么懂得哈希表 ,哈希表是什么摘自百度：散列表（Hash table,也叫哈希表） ,是依据关键码值 Key value而直接进行拜访的数据结构；也就是说, 它通过把关键码值映射到表中一个位置来拜访记录,以加快查找的速度； 这个映射函数叫做散列函数,存放记录的数组叫做散列表；给定表 M ,存在函数 fkey,对任意给定的关键字值 key,代入函数后如能得到包含该关键字的记录在表中的地址,就称表 M 为哈希 Hash）表,函数 fkey为哈希 Hash 函数4. 请写出以下算法的时间复杂度冒泡排序法 插入排序法 堆排序法

5、 二叉树排序法On2）On2 Onlog2 n 最差 On2平均 On*log2n 快速排序法 希尔排序法最差 On2平均 On*log2n Onlog n不稳固5. 数据结构,二叉树的相关学问,开销量,为何使用二叉树等；在运算机科学中, 二叉树是每个结点最多有两个子树的有序树；通常根的子树被称作“ 左子树 ”（ left subtree ）和“ 右子树 ”（ right subtree ）；二叉树常被用作二叉查找树和二叉堆或是二叉排序树；二叉树的每个结点至多只有二棵子树不存在出度大于2 的结点 ,二叉树的子树有左右之分,次序不能颠倒；文件系统和数据库系统一般都采纳树（特殊是 B 树）的数据结

6、构数据, 主要为排序和检索的效率； 二叉树是一种最基本最典型的排序树,用于教学和争论树的特性,本身很少在实际中进行应用,由于缺点太明显了（看看教科书怎么说的）虽然由于效率问题并不有用,单不失一种教学例子的好手段；四、编程题1. 编写一个程序,把一个有序整数数组放在二叉树中；#include #include #include struct student int value; struct student *lchild; ；就像冒泡排序一样,名师归纳总结 - - - - - - -第 2 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆struct

7、 student *rchild; ; void arraytotreeint *a, int len, struct student *p iflen *p = struct student*mallocsizeofstruct student; *p-value = alen/2; arraytotreea, len/2, &*p-lchild; arraytotreea+len/2+1, len-len/2-1, &*p-rchild; else *p = NULL; void display_treestruct student *head ifhead-lchilddisplay_t

8、reehead-lchild; printf%d, head-value; ifhead-rchilddisplay_treehead-rchild; int main int a = 1,2,3,4,9,10,33,56,78,90; struct student *tree; arraytotreea, sizeofa/sizeofa0, &tree; printfAfter convert:n; display_treetree; printfn; return 0; 2. 在二叉查找树中查找某一个值所在的位置；int find_btreebtree *bt, datatype x if

9、bt ifbt-key = x return TRUE; if.find_btreebt-lchild,x 名师归纳总结 - - - - - - -第 3 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆if.find_btreebt-rchild,x return FALSE; 3.二叉树,比父节点大的元素,都在右子树,比父节点小的元素都在左子树；也就是排序二叉树,写出插入一个节点或者删除一个节点；#include #include #include #include #define TRUE 1 #define FALSE 0 typedef i

10、nt status; typedef int datatype; typedef struct node datatype key; struct node *lchild, *rchild; btree; void bst_insertbtree *bt, datatype key / 二叉排序树的插入 ifNULL = *bt btree *node = mallocsizeofbtree; node-key = key; node-lchild = node-rchild = NULL; *bt = node; else ifkey *bt-key bst_insert&*bt-rchi

11、ld, key; else bst_insert&*bt-lchild, key; 名师归纳总结 status bst_deletebtree *bt, datatype key / 二叉排序树的删除第 4 页,共 49 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 btree *tmp = NULL; if.*bt return FALSE; else ifkey key / 在左子树中找 bst_delete&*bt-lchild, key; else ifkey *bt-key / 在右子树中找 bst_delete&*bt-r

12、child, key; else / 找到了 tmp = *bt; if.*bt-lchild / 左子树为空 *bt = *bt-rchild; else if.*bt-rchild / 右子树为空 *bt = *bt-lchild; freetmp; return TRUE; void preorder_btreebtree *bt / 二叉树的先序遍历 ifbt .= NULL printf%d,bt-key; preorder_btreebt-lchild; preorder_btreebt-rchild; 名师归纳总结 void inorder_btreebtree *bt/二叉树的

13、中序遍历第 5 页,共 49 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 ifbt .= NULL inorder_btreebt-lchild; printf%d,bt-key; inorder_btreebt-rchild; int main int argc, char *argv btree *bt = NULL; int n; while1 scanf%d,&n; ifn = 0 / 输入 0 就终止 break; else bst_insert&bt, n; preorder_btreebt; putcharn; bst

14、_delete&bt, 8; preorder_btreebt; putcharn; return 0; 4. 实现单向链表 :创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链 表节点简洁的链表操作,这里假设链表无头结点；可以自己完善有头结点的单向链表；头文件：/* list.h - header file for a simple list type */ #ifndef _LIST_H_ #define _LIST_H_ #include #include #include 名师归纳总结 - - - - - - -第 6 页,共 49 页精选学习资料 - - - - - -

15、- - - 学而不思就惘,思而不学就殆#include /* C99 feature */ #ifdef _cplusplus extern C #endif/*_cplusplus*/ /* program-specific declarations */ typedef int dataType; /* general type definitions */ typedef dataType Item; typedef struct node Item item; struct node * next; Node; typedef Node * List; /* function prot

16、otypes */ void ListCreateList * plist; bool ListIsEmptyconst List *plist; bool ListIsFullconst List *plist; unsigned int ListItemCountconst List *plist; bool AddItemItem item, List * plist; void EmptyTheListList * plist; void TraverseTheListList * plist; unsigned int ListItemSearchconst List * plist

17、,const Item item; void deleteTheListNodeList * plist,unsigned int num; #ifdef _cplusplus #endif/*_cplusplus*/ #endif /*_LIST_H_*/ .c 文件 /*list.c - functions supporting list operations */ #include #include #include list.h 名师归纳总结 - - - - - - -第 7 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆/* local

18、function definition */ static void CopyToNodeconst Item item, Node * pnode; static void displayTheNOdeconst Node * pnode; static bool ItemIsEquconst Item Item, const Node * pnode; /*init a empty list*/ void ListCreateList * plist * plist = NULL; /* returns true if list is empty */ bool ListIsEmptyco

19、nst List * plist if *plist = NULL return true; else return false; /* returns true if list is full */ bool ListIsFullconst List * plist Node * pt; bool full; pt = Node * mallocsizeofNode; if pt = NULL full = true; else full = false; freept; return full; /* returns number of nodes */ unsigned int List

20、ItemCountconst List * plist unsigned int count = 0; Node * pnode = *plist; 名师归纳总结 - - - - - - -第 8 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆while pnode .= NULL +count; pnode = pnode-next; return count; /*search item in the list */ unsigned int ListItemSearchconst List * plist,const Item item in

21、t num = 0; Node * pnode = *plist; while pnode .= NULL num+; ifItemIsEquitem, pnode return num; pnode = pnode-next; return 0; /* creates node to hold item and adds it to the end of list*/ bool AddItemItem item, List * plist Node * pnew = NULL; Node * scan = *plist; pnew = Node * mallocsizeofNode; if

22、pnew = NULL return false; CopyToNodeitem, pnew; pnew-next = NULL; if scan = NULL /* empty list, so place */ *plist = pnew; /* pnew at head of list */ else 名师归纳总结 - - - - - - -第 9 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆while scan-next .= NULL scan = scan-next; /* find end of list */ */ scan-ne

23、xt = pnew; /* add pnew to end return true; /*delete the node by num*/ void deleteTheListNodeList * plist,unsigned int num Node * pnode = *plist; Node * psave = NULL; ifListIsEmptyplist return; if1 = num psave = *plist; *plist = psave-next; freepsave; return ; -num; whilepnode-next .= NULL & num 1 -n

24、um; pnode = pnode-next; ifpnode-next .= NULL & 1 = num psave = pnode-next; pnode-next = psave-next; freepsave; /*Traverse The List */ void TraverseTheListList * plist Node * pnode = *plist; while pnode .= NULL displayTheNOdepnode; 名师归纳总结 - - - - - - -第 10 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学

25、就殆pnode = pnode-next; putcharn; /* free memory allocated by malloc */ void EmptyTheListList * plist Node * psave = NULL; while *plist .= NULL psave = *plist-next; /* save address of next node */ free*plist; /* free current node */ *plist = psave; /* advance to next node */ /* local function definiti

26、on */ /* copies an item into a node */ static void CopyToNodeconst Item item, Node * pnode pnode-item = item; /* structure copy */ /* display a node data*/ static void displayTheNOdeconst Node * pnode printf%d ,pnode-item; /*To determine the node*/ static bool ItemIsEquconst Item Item, const Node *

27、pnode return Item = pnode-item .true :false; 5. 编程实现判定一个链表是否是递增的假设链表无头结点 .如链表为空默认为递增；思路之前结点的数据与之后的数据依次比 较typedef int dataType; /* general type definitions */ typedef dataType Item; 名师归纳总结 - - - - - - -第 11 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆typedef struct node Item item; struct node * nex

28、t; Node; typedef Node * List; bool listItemIsIncreaseList * plist Node * preptr = *plist; Node * curptr = NULL; ifNULL = *plist return true; curptr = preptr-next; whilecurptr .= NULL ifpreptr-item curptr-item /* 假如是严格递增,就判定用= */ break; preptr = curptr; curptr = curptr-next; return curptr = NULL.true

29、 :false; 6. 编程实现删除链表中的重复节点假设链表无头结点,挨个遍历链表数据,与之后的结点依次比较,发觉重复的就删除typedef int dataType; /* general type definitions */ typedef dataType Item; typedef struct node Item item; struct node * next; Node; typedef Node * List; void delRepeatedNodeOnceList * plist 名师归纳总结 Node *p=*plist,*q,*u,*y; 第 12 页,共 49 页-

30、 - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆whilep q=p-next; u=p; whileq ifq-item = p-item u-next=q-next;y=q; q=q-next; freey; else u=q; q=q-next; p=p-next; 7. 只遍历一次链表,实现链表的倒序假设链表无头节点,链表头插入,直到遍历到链表末尾typedef int dataType; /* general type definitions */ typedef dataType Item; typedef struct node

31、 Item item; struct node * next; Node; typedef Node * List; void ListInverse List * plist Node *pnode = *plist; Node *pcur = NULL; Node *ptmp = NULL; ifNULL = pnode | NULL = pnode-next return ; 名师归纳总结 - - - - - - -第 13 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆pcur = pnode-next; pnode-next = NULL

32、; while pcur.= NULL ptmp = pcur-next; pcur-next = *plist; *plist = pcur; pcur = ptmp; 8.将两个有序链表A1,A2 表合并为一个有序链表A3 假设链表无头节点,简洁递增序列,思路：链表插入排序typedef int dataType; /* general type definitions */ typedef dataType Item; typedef struct node Item item; struct node * next; Node; typedef Node * List; void Li

33、stMergeList * A1, List *A2,List *A3 Node *p = *A1; Node *q = *A2; Node *t = *A1; *A3 = *A1; ifNULL = p *A3 = *A2; ifNULL = q *A3 = *A1; p = p-next; whileq .= NULL & p .= NULL 名师归纳总结 - - - - - - -第 14 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 ifp-item item t-next = p; t = p; p = p-next; else t-n

34、ext = q; t = q; q = q-next; ifq .= NULL t-next = q; else t-next = p; 9. 已知链表节点struct LNode int iValue; LNode *next; ; 已创建一个有序的链表,序；请实现以下函数：从小到大排列； 实现以下函数, 将数据插入到链表中,并且有bool InsertLinkLinkList *p,int a; 思路：该题未说明有无头结点,且次序未知, 这里假设为递增序列,简洁遍历比较插入；/* 将 data 插入到递增有序的链表中,使该链表仍保持递增有序 */ bool InsertLinkLinkLi

35、st *p,int a LNode *pre=NULL, *temp=NULL; temp = LNode *mallocsizeofLNode; ifNULL =temp fprintfstderr,malloc failedn return false; temp-iValue= a; temp-next = NULL; 名师归纳总结 - - - - - - -第 15 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆/* 搜寻链表,找到插入位置 */ forpre=p; pre-next.=NULL & pre-next-iValue next

36、; /* 插入新结点 */ temp-next = pre-next; pre-next = temp; return true; 10.写一个链表,实现创建链表,添加链表节点,删除链表节点,查找链表节点,写一个,再删除main 函数,创建一个链表,里面添加20 个同学节点（节点含有姓名和学号）其中任意一个节点,输出任意指定节点,输出最终10 名同学节点；头文件：/* list.h - header file for a simple list type */ #ifndef _LIST_H_ #define _LIST_H_ #include #include #include #inclu

37、de /* C99 feature */ #ifdef _cplusplus extern C #endif/*_cplusplus*/ /* program-specific declarations */ typedef struct stu int num; char name20; dataType; /* general type definitions */ typedef dataType Item; typedef struct node Item item; struct node * next; Node; typedef Node * List; 名师归纳总结 - - -

38、 - - - -第 16 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆/* function prototypes */ void ListCreateList * plist; bool ListIsEmptyconst List *plist; bool ListIsFullconst List *plist; unsigned int ListItemCountconst List *plist; bool AddItemItem item, List * plist; void EmptyTheListList * plist; void TraverseTheListList * plist; unsigned int ListItemSearchconst List * plist,const Item item; Node * ListNodeSearchconst List * plist,unsigned int num; void deleteTheListNodeList * plist,unsigned int num; void dsiplayNodeconst List * plist,const unsigned int num; #ifdef _cplusplus