数据结构笔试题答案.doc

。数据结构笔试题答案一、 选择题1. C插入排序从后面插入的时候，只要把8和9交换一下就行了，遍历到前面都不再有任何操作。冒泡排序第一次循环把9沉到最后面，然后第二次循环发现没有任何交换操作，说明已经排好序了。2. A3. D已知前序和后序不能唯一确定4. B5. 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. EACBDGF3.sort_b_tree(&(*tree)-right),s)sort_b_tree(&(*tree)-left),s)三、 简答题1. 数组和链表的区别，请详细解释。从逻辑结构来看：a) 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。b) 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素从内存存储来看：a) (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小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(nlogn)不稳定5. 数据结构，二叉树的相关知识，开销量，为何使用二叉树等。在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。文件系统和数据库系统一般都采用树（特别是B树）的数据结构数据，主要为排序和检索的效率。二叉树是一种最基本最典型的排序树，用于教学和研究树的特性，本身很少在实际中进行应用，因为缺点太明显了（看看教科书怎么说的）。就像冒泡排序一样，虽然因为效率问题并不实用，单不失一种教学例子的好手段。四、 编程题1. 编写一个程序，把一个有序整数数组放在二叉树中。#include #include #include struct student int value; struct student *lchild; 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)if(!find_btree(bt-rchild,x)return FALSE;3. 二叉树，比父节点大的元素，都在右子树，比父节点小的元素都在左子树。也就是排序二叉树，写出插入一个节点或者删除一个节点。#include #include #include #include #define TRUE 1#define FALSE 0typedef int status;typedef int datatype;typedef struct nodedatatype 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);elsebst_insert(&(*bt)-lchild, key);status bst_delete(btree *bt, datatype key)/二叉排序树的删除btree *tmp = NULL;if(!*bt)return FALSE;elseif(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)/二叉树的中序遍历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;elsebst_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 #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/* 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; 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 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); 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;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;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);elseu=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 ;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 )if(p-item item)t-next = p;t = p;p = p-next;elset-next = q;t = q;q = q-next;if(q != NULL )t-next = q;elset-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; /* 搜索链表，找到插入位置 */ 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 stuint num;char name20; 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);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) 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) 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)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 */ 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);elsefprintf(stderr,no such node .n);/* 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(NUM:%d NAME:%sn,pnode-item.num,);/*To determine the node*/static bool ItemIsEqu(const Item Item, const Node * pnode)return Item.num = pnode-item.num ?true :false;测试文件：#include #include #include #include #include list.hint main()/ for test 1puts(for test 1);List list;Item item;int i = 0;ListCreate(&list);/instert 20 stus infomationfor(i = 1;i=20;i+)/make the item :the stu info,num:1-20 ,