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

精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构笔试题答案一、挑选题1. C 插入排序从后面插入的时候,操作；只要把 8 和 9 交换一下就行了, 遍历到前面都不再有任何冒泡排序第一次循环把 9 沉到最终面,然后其次次循环发觉没有任何交换操作,说明已经排好序了；2. A 3. D 已知前序和后序不能唯独确定4. B 5. D 二、填空题1.2.1.=null 2p->next 3r.=null 4r->data < q->data 5r->next 6p->next 题中 p 指向无序区第一个记录,q 指向最小值结点,一趟排序终止,p 和 q 所指结点值交换,同时向后移p 指针；EACBDGF 3.sort_b_tree&*tree->right,s sort_b_tree&*tree->left,s 三、简答题1. 数组和链表的区分,请具体说明；从规律结构来看：a数组必需事先定义固定的长度（元素个数）,不能适应数据动态地增减的情形；当数据增加时,可能超出原先定义的元素个数；可以依据下标直接存取；当数据削减时, 造成内存铺张；数组b 链表动态地进行储备安排,可以适应数据动态地增减的情形,且可以便利地插入、删除数据项；（数组中插入、删除数据项时,需要移动其它数据项,特别繁琐）链表必需依据 next 指针找到下一个元素从内存储备来看：名师归纳总结 a静态 数组从栈中安排空间, 对于程序员便利快速,但是自由度小第 1 页,共 49 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆b链表从堆中安排空间, 自由度大但是申请治理比较麻烦从上面的比较可以看出,假如需要快速拜访数据,很少或不插入和删除元素,就应当用数组；相反,假如需要常常插入和删除元素就需要用链表数据结构了；2. 排序算法有哪些？< C语言总共有多少种排序法 > 排序算法有许多,每种算法有不同的时间和空间复杂度,效率也有差别, 那么针对使用上也有不同的场合；原就上说, 数据结构是一门领域,跟语言没有确定的联系,许多时候同样的算法可以用许多种语言实现；下面列一些常见的算法：插入排序,冒泡排序,挑选排序,快速排序,堆排序,归并排序,基数排序,希尔排序等；3. 怎么懂得哈希表 ,哈希表是什么摘自百度：散列表（Hash table,也叫哈希表） ,是依据关键码值 Key value而直接进行拜访的数据结构；也就是说, 它通过把关键码值映射到表中一个位置来拜访记录,以加快查找的速度； 这个映射函数叫做散列函数,存放记录的数组叫做散列表；给定表 M ,存在函数 fkey,对任意给定的关键字值 key,代入函数后如能得到包含该关键字的记录在表中的地址,就称表 M 为哈希 Hash）表,函数 fkey为哈希 Hash 函数4. 请写出以下算法的时间复杂度冒泡排序法 插入排序法 堆排序法 二叉树排序法On2）On2 Onlog2 n 最差 On2平均 On*log2n 快速排序法 希尔排序法最差 On2平均 On*log2n Onlog n不稳固5. 数据结构,二叉树的相关学问,开销量,为何使用二叉树等；在运算机科学中, 二叉树是每个结点最多有两个子树的有序树；通常根的子树被称作“ 左子树 ”（ left subtree ）和“ 右子树 ”（ right subtree ）；二叉树常被用作二叉查找树和二叉堆或是二叉排序树；二叉树的每个结点至多只有二棵子树不存在出度大于2 的结点 ,二叉树的子树有左右之分,次序不能颠倒；文件系统和数据库系统一般都采纳树（特殊是 B 树）的数据结构数据, 主要为排序和检索的效率； 二叉树是一种最基本最典型的排序树,用于教学和争论树的特性,本身很少在实际中进行应用,由于缺点太明显了（看看教科书怎么说的）虽然由于效率问题并不有用,单不失一种教学例子的好手段；四、编程题1. 编写一个程序,把一个有序整数数组放在二叉树中；#include <stdio.h> #include <stdlib.h> #include <string.h> struct student int value; struct student *lchild; ；就像冒泡排序一样,名师归纳总结 - - - - - - -第 2 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆struct 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_treehead->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; printf"After convert:n" display_treetree; printf"n" return 0; 2. 在二叉查找树中查找某一个值所在的位置；int find_btreebtree *bt, datatype x ifbt ifbt->key = x return TRUE; if.find_btreebt->lchild,x 名师归纳总结 - - - - - - -第 3 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆if.find_btreebt->rchild,x return FALSE; 3.二叉树,比父节点大的元素,都在右子树,比父节点小的元素都在左子树；也就是排序二叉树,写出插入一个节点或者删除一个节点；#include <stdio.h> #include <stdlib.h> #include <strings.h> #include <assert.h> #define TRUE 1 #define FALSE 0 typedef int 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->rchild, key; else bst_insert&*bt->lchild, key; 名师归纳总结 status bst_deletebtree *bt, datatype key / 二叉排序树的删除第 4 页,共 49 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 btree *tmp = NULL; if.*bt return FALSE; else ifkey < *bt->key / 在左子树中找 bst_delete&*bt->lchild, key; else ifkey > *bt->key / 在右子树中找 bst_delete&*bt->rchild, 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/二叉树的中序遍历第 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; putchar'n' bst_delete&bt, 8; preorder_btreebt; putchar'n' return 0; 4. 实现单向链表 :创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链 表节点简洁的链表操作,这里假设链表无头结点；可以自己完善有头结点的单向链表；头文件：/* list.h - header file for a simple list type */ #ifndef _LIST_H_ #define _LIST_H_ #include <stdio.h> #include <string.h> #include <stdlib.h> 名师归纳总结 - - - - - - -第 6 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆#include <stdbool.h> /* 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 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; void deleteTheListNodeList * plist,unsigned int num; #ifdef _cplusplus #endif/*_cplusplus*/ #endif /*_LIST_H_*/ .c 文件 /*list.c - functions supporting list operations */ #include <stdio.h> #include <stdlib.h> #include "list.h" 名师归纳总结 - - - - - - -第 7 页,共 49 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆/* local 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 ListIsEmptyconst 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 ListItemCountconst 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 int 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 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->next = 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 -num; 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 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆pnode = pnode->next; putchar'n' /* 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 definition */ /* 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 * 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 * next; 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 :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 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆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 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; 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 ListMergeList * 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 < q->item t->next = p; t = p; p = p->next; else t->next = 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 InsertLinkLinkList *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 < a; pre=pre->next; /* 插入新结点 */ 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 <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> /* 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; 名师归纳总结 - - - - - - -第 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