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

学而不思则惘，思而不学则殆数据结构笔试题答案一、选择题1.C 插入排序从后面插入的时候，只要把 8 和 9 交换一下就行了，遍历到前面都不再有任何操作。冒泡排序第一次循环把9 沉到最后面，然后第二次循环发现没有任何交换操作，说明已经排好序了。2.A 3.D 已知前序和后序不能唯一确定4.B 5.D 二、填空题1.(1)!=null (2)p-next (3)r!=null (4)r-data data (5)r-next (6)p-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)(静态 )数组从栈中分配空间, 对于程序员方便快速,但是自由度小精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 49 页学而不思则惘，思而不学则殆b)链表从堆中分配空间, 自由度大但是申请管理比较麻烦从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反，如果需要经常插入和删除元素就需要用链表数据结构了。2.排序算法有哪些？ 排序算法有很多，每种算法有不同的时间和空间复杂度，效率也有差别， 那么针对使用上也有不同的场合。原则上说， 数据结构是一门领域，跟语言没有绝对的联系，很多时候同样的算法可以用很多种语言实现。下面列一些常见的算法：插入排序，冒泡排序，选择排序，快速排序，堆排序，归并排序，基数排序，希尔排序等。3.怎么理解哈希表,哈希表是什么摘自百度：散列表（Hash table，也叫哈希表） ，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说， 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表 M ，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M 为哈希 (Hash）表，函数f(key)为哈希 (Hash) 函数4.请写出以下算法的时间复杂度冒泡排序法插入排序法堆排序法二叉树排序法O(n2）O(n2) O(nlog2 n) 最差 O(n2)平均 O(n*log2n) 快速排序法希尔排序法最差 O(n2)平均 O(n*log2n) O(nlog n)不稳定5.数据结构，二叉树的相关知识，开销量，为何使用二叉树等。在计算机科学中， 二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“ 左子树 ” （left subtree ）和“ 右子树 ” （ right subtree ） 。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2 的结点 )，二叉树的子树有左右之分，次序不能颠倒。文件系统和数据库系统一般都采用树（特别是 B树）的数据结构数据，主要为排序和检索的效率。 二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序一样，虽然因为效率问题并不实用，单不失一种教学例子的好手段。四、编程题1.编写一个程序，把一个有序整数数组放在二叉树中。#include #include #include struct student int value; struct student *lchild; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 49 页学而不思则惘，思而不学则殆struct student *rchild; ; void arraytotree(int *a, int len, struct student *p) if(len) *p = (struct student*)malloc(sizeof(struct student); (*p)-value = alen/2; arraytotree(a, len/2, &(*p)-lchild); arraytotree(a+len/2+1, len-len/2-1, &(*p)-rchild); else *p = NULL; void display_tree(struct student *head) if(head-lchild)display_tree(head-lchild); printf(%d, head-value); if(head-rchild)display_tree(head-rchild); int main() int a = 1,2,3,4,9,10,33,56,78,90; struct student *tree; arraytotree(a, sizeof(a)/sizeof(a0), &tree); printf(After convert:n); display_tree(tree); printf(n); return 0; 2.在二叉查找树中查找某一个值所在的位置。int find_btree(btree *bt, datatype x) if(bt) if(bt-key = x) return TRUE; if(!find_btree(bt-lchild,x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 49 页学而不思则惘，思而不学则殆if(!find_btree(bt-rchild,x) return FALSE; 3.二叉树，比父节点大的元素，都在右子树，比父节点小的元素都在左子树。也就是排序二叉树，写出插入一个节点或者删除一个节点。#include #include #include #include #define TRUE 1 #define FALSE 0 typedef int status; typedef int datatype; typedef struct node datatype key; struct node *lchild, *rchild; btree; void bst_insert(btree *bt, datatype key) / 二叉排序树的插入 if(NULL = *bt) btree *node = malloc(sizeof(btree); node-key = key; node-lchild = node-rchild = NULL; *bt = node; else if(key (*bt)-key) bst_insert(&(*bt)-rchild, key); else bst_insert(&(*bt)-lchild, key); status bst_delete(btree *bt, datatype key) / 二叉排序树的删除精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 49 页学而不思则惘，思而不学则殆 btree *tmp = NULL; if(!*bt) return FALSE; else if(key key) / 在左子树中找 bst_delete(&(*bt)-lchild, key); else if(key (*bt)-key) / 在右子树中找 bst_delete(&(*bt)-rchild, key); else / 找到了 tmp = *bt; if(!(*bt)-lchild) / 左子树为空 *bt = (*bt)-rchild; else if(!(*bt)-rchild) / 右子树为空 *bt = (*bt)-lchild; free(tmp); return TRUE; void preorder_btree(btree *bt) / 二叉树的先序遍历 if(bt != NULL) printf(%d,bt-key); preorder_btree(bt-lchild); preorder_btree(bt-rchild); void inorder_btree(btree *bt)/二叉树的中序遍历精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 49 页学而不思则惘，思而不学则殆 if(bt != NULL) inorder_btree(bt-lchild); printf(%d,bt-key); inorder_btree(bt-rchild); int main (int argc, char *argv) btree *bt = NULL; int n; while(1) scanf(%d,&n); if(n = 0) / 输入 0 则结束 break; else bst_insert(&bt, n); preorder_btree(bt); putchar(n); bst_delete(&bt, 8); preorder_btree(bt); putchar(n); return 0; 4.实现单向链表:创建链表、插入链表、查询链表、删除特定序号链表节点、遍历剩余链表节点简单的链表操作，这里假设链表无头结点。可以自己完善有头结点的单向链表。头文件：/* list.h - header file for a simple list type */ #ifndef _LIST_H_ #define _LIST_H_ #include #include #include 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 49 页学而不思则惘，思而不学则殆#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 prototypes */ void ListCreate(List * plist); bool ListIsEmpty(const List *plist); bool ListIsFull(const List *plist); unsigned int ListItemCount(const List *plist); bool AddItem(Item item, List * plist); void EmptyTheList(List * plist); void TraverseTheList(List * plist); unsigned int ListItemSearch(const List * plist,const Item item); void deleteTheListNode(List * 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 function definition */ static void CopyToNode(const Item item, Node * pnode); static void displayTheNOde(const Node * pnode); static bool ItemIsEqu(const Item Item, const Node * pnode); /*init a empty list*/ void ListCreate(List * plist) * plist = NULL; /* returns true if list is empty */ bool ListIsEmpty(const List * plist) if (*plist = NULL) return true; else return false; /* returns true if list is full */ bool ListIsFull(const List * plist) Node * pt; bool full; pt = (Node *) malloc(sizeof(Node); if (pt = NULL) full = true; else full = false; free(pt); return full; /* returns number of nodes */ unsigned int ListItemCount(const 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 ListItemSearch(const List * plist,const Item item) int num = 0; Node * pnode = *plist; while (pnode != NULL) num+; if(ItemIsEqu(item, pnode) return num; pnode = pnode-next; return 0; /* creates node to hold item and adds it to the end of list*/ bool AddItem(Item item, List * plist) Node * pnew = NULL; Node * scan = *plist; pnew = (Node *) malloc(sizeof(Node); if (pnew = NULL) return false; CopyToNode(item, 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 deleteTheListNode(List * plist,unsigned int num) Node * pnode = *plist; Node * psave = NULL; if(ListIsEmpty(plist) return; if(1 = num) psave = *plist; *plist = psave-next; free(psave); return ; -num; while(pnode-next != NULL & num 1) -num; pnode = pnode-next; if(pnode-next != NULL & 1 = num) psave = pnode-next; pnode-next = psave-next; free(psave); /*Traverse The List */ void TraverseTheList(List * plist) Node * pnode = *plist; while (pnode != NULL) displayTheNOde(pnode); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 49 页学而不思则惘，思而不学则殆pnode = pnode-next; putchar(n); /* free memory allocated by malloc() */ void EmptyTheList(List * 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 CopyToNode(const Item item, Node * pnode) pnode-item = item; /* structure copy */ /* display a node data*/ static void displayTheNOde(const Node * pnode) printf(%d ,pnode-item); /*To determine the node*/ static bool ItemIsEqu(const 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 listItemIsIncrease(List * plist) Node * preptr = *plist; Node * curptr = NULL; if(NULL = *plist) return true; curptr = preptr-next; while(curptr != NULL) if(preptr-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 delRepeatedNodeOnce(List * plist) Node *p=*plist,*q,*u,*y; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 49 页学而不思则惘，思而不学则殆while(p) q=p-next; u=p; while(q) if(q-item = p-item) u-next=q-next;y=q; q=q-next; free(y); 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; if(NULL = 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 ListMerge(List * A1, List *A2,List *A3) Node *p = *A1; Node *q = *A2; Node *t = *A1; *A3 = *A1; if(NULL = p) *A3 = *A2; if(NULL = q) *A3 = *A1; p = p-next; while(q != NULL & p != NULL ) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 49 页学而不思则惘，思而不学则殆 if(p-item item) t-next = p; t = p; p = p-next; else t-next = q; t = q; q = q-next; if(q != NULL ) t-next = q; else t-next = p; 9.已知链表节点struct LNode int iValue; LNode *next; ; 已创建一个有序的链表，从小到大排列。 实现以下函数，将数据插入到链表中，并且有序。请实现以下函数：bool InsertLink(LinkList *p,int a); 思路：该题未说明有无头结点，且顺序未知， 这里假设为递增序列，简单遍历比较插入。/* 将 data 插入到递增有序的链表中，使该链表仍保持递增有序*/ bool InsertLink(LinkList *p,int a) LNode *pre=NULL, *temp=NULL; temp = (LNode *)malloc(sizeof(LNode); if(NULL =temp ) fprintf(stderr,malloc failedn) return false; temp-iValue= a; temp-next = NULL; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 49 页学而不思则惘，思而不学则殆/* 搜索链表，找到插入位置*/ for(pre=p; pre-next!=NULL & pre-next-iValue 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 #include #include #include /* 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 ListCreate(List * plist); bool ListIsEmpty(const List *plist); bool ListIsFull(const List *plist); unsigned int ListItemCount(const List *plist); bool AddItem(Item item, List * plist); void EmptyTheList(List * plist); void TraverseTheList(List * plist); unsigned int ListItemSearch(const List * plist,const Item item); Node * ListNodeSearch(const List * plist,unsigned int num); void deleteTheListNode(List * plist,unsigned int num); void dsiplayNode(const List * plist,const unsigned int num); #ifdef _cplusplus #endif/*_cplusplus*/ #endif /*_LIST_H_*/ C：文件/* list.c - functions supporting list operations */ #include #include #include list.h /* local function definition */ static void CopyToNode(const Item item, Node * pnode); static void displayTheNOde(const Node * pnode); static bool ItemIsEqu(const Item Item, const Node * pnode); /*init a empty list*/ void ListCreate(List * plist) * plist = NULL; /* returns true if list is empty */ bool ListIsEmpty(const List * plist) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 49 页学而不思则惘，思而不学则殆if (*plist = NULL) return true; else return false; /* returns true if list is full */ bool ListIsFull(const List * plist) Node * pt; bool full; pt = (Node *) malloc(sizeof(Node); if (pt = NULL) full = true; else full = false; free(pt); return full; /* returns number of nodes */ unsigned int ListItemCount(const List * plist) unsigned int count = 0; Node * pnode = *plist; while (pnode != NULL) +count; pnode = pnode-next; return count; /*search item in the list */ unsigned int ListItemSearch(const List * plist,const Item item) int num = 0; Node * pnode = *plist; while (pnode != NULL) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 49 页学而不思则惘，思而不学则殆num+; if(ItemIsEqu(item, pnode) return num; pnode = pnode-next; return 0; /* creates node to hold item and adds it to the end of list*/ bool AddItem(Item item, List * plist) Node * pnew = NULL; Node * scan = *plist; pnew = (Node *) malloc(sizeof(Node); if (pnew = NULL) return false; CopyToNode(item, pnew); pnew-next = NULL; if (scan = NULL) /* empty list, so place */ *plist = pnew; /* pnew at head of list */ else 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 deleteTheListNode(List * plist,unsigned int num) Node * pnode = *plist; Node * psave = NULL; if(ListIsEmpty(plist) return; if(1 = num) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 49 页学而不思则惘，思而不学则殆psave = *plist; *plist = psave-next; free(psave); return ; -num; while(pnode-next != NULL & num 1) -num; pnode = pnode-next; if(pnode-next != NULL & 1 = num) psave = pnode-next; pnode-next = psave-next; free(psave); /*Traverse The List */ void TraverseTheList(List * plist) Node * pnode = *plist; while (pnode != NULL) displayTheNOde(pnode); pnode = pnode-next; putchar(n); /* free memory allocated by malloc() */ void EmptyTheList(List * 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 */ 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 49 页学而不思则惘，思而不学则殆 Node * ListNodeSearch(const List * plist, unsigned int num) Node * pnode = *plist; while(pnode != NULL & num 1) -num; pnode = pnode-next; return pnode; void dsiplayNode(const List * plist,unsigned int num) Node * pnode = *plist; while(pnode != NULL & num 1) -num; pnode = pnode-next; if(pnode != NULL) displayTheNOde(pnode);