数据结构___头插法和尾插法建立链表(各分有无头结点)

2009～2010学年第二学期期末考试《数据结构》试题A一、选择题（每题2分，15题，共30分，请将答案写到后附答题纸的表格内）1、在数据结构的讨论中把数据结构从逻辑上分为（）A ）内部结构与外部结构 B）静态结构与动态结构C ）线性结构与非线性结构D ）紧凑结构与非紧凑结构。

2、对线性表进行二分查找时，要求线性表必须（）。

A. 以链接方式存储,且数据元素有序B. 以链接方式存储C. 以顺序方式存储,且数据元素有序D. 以顺序方式存储3、若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（）A）O(n) B）O(1) C）O(n2) D）O(n3)4、顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（）A）5和1 B）2和4 C）1和5 D）4和25．在下列排序方法中，（）的比较次数与记录的初始排列状态无关。

A. 直接插入排序B. 起泡排序C. 快速排序D. 简单选择排序6、设有数组A[i，j],数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的存储首地址为( )A）BA+41 B）BA+180 C）BA+222 D）BA+2257、下面哪个术语与数据的存储结构无关（）A）顺序表B）链表C）散列表D）队列8、在一棵高度为k的满二叉树中，结点总数为（）A）2k-1 B）2k C）2k-1D）⎣log2k⎦+19、一棵完全二叉树上有1001个结点，其中叶子结点的个数为（）A）250 B）500 C）254 D）50110、利用二叉链表存储树，则根结点的右指针是（）A）指向最左孩子 B）指向最右孩子 C）空 D）非空11、若邻接表中有奇数个边结点，则一定（）A）图中有奇数个顶点B）图中有偶数个顶点C）图为无向图D）图为有向图12、无向图G=（V，E），其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是（）A）abecdf B）acfebd C）aebcfd D）aedfcb13、在一个带权连通图G中，权值最小的边一定包含在G的（）A）最小生成树中B）深度优先生成树中C）广度优先生成树中D）深度优先生成森林中14、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）A）1.0 B）2.9 C）3.4 D）5.515、下面的序列中初始序列构成最小堆（小根堆）的是（）A）10、60、20、50、30、26、35、40 B）70、40、36、30、20、16、28、10C）20、60、50、40、30、10、8、72 D）10、30、20、50、40、26、35、60 二、应用题（6题，共50分）1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，n m个度为m的结点，问该树中有多少个叶子结点？要求写出分析过程。

国家开放大学电大《数据结构》网络课单项选择题题库及答案单项选择题题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

选择一项：A. 算法的具体实现B. 逻辑结构C. 给相关变量分配存储单元D. 物理结构题目2下列说法中，不正确的是（）。

选择一项：A. 数据项是数据中不可分割的最小可标识单位B. 数据元素是数据的基本单位C. 数据项可由若干个数据元素构成D. 数据可有若干个数据元素构成题目3一个存储结点存储一个（）。

选择一项：A. 数据项B. 数据类型C. 数据元素D. 数据结构题目4数据结构中，与所使用的计算机无关的是数据的（）。

选择一项：A. 存储结构B. 物理结构C. 逻辑结构D. 物理和存储结构题目5在线性表的顺序结构中，以下说法正确的是（）。

选择一项：A. 进行数据元素的插入、删除效率较高B. 数据元素是不能随机访问的C. 逻辑上相邻的元素在物理位置上不一定相邻D. 逻辑上相邻的元素在物理位置上也相邻题目6对链表, 以下叙述中正确的是（）。

选择一项：A. 可以通过下标对链表进行直接访问B. 插入删除元素的操作一定要要移动结点C. 不能随机访问任一结点D. 结点占用的存储空间是连续的题目7下列的叙述中，不属于算法特性的是（）。

选择一项：A. 可行性B. 有穷性C. 可读性D. 输入性题目8算法的时间复杂度与（）有关。

选择一项：A. 所使用的计算机B. 计算机的操作系统C. 数据结构D. 算法本身题目9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

选择一项：A. n-i-1B. iC. n-i+1D. n-i题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

选择一项：A. iB. n-i-1C. n-iD. n-i+1题目11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

#include "stdio.h"#include "stdlib.h"typedef struct List{int data;struct List *next; //指针域}List;void HeadCreatList (List *L) //头插法建立链表{List *s;L->next=NULL;for (int i=0;i<10;i++){s=(struct List*)malloc(sizeof(struct List));s->data=i;s->next=L->next; //将L指向的地址赋值给S;L->next=s;}}void TailCreatList(List *L) //尾插法建立链表{List *s,*r;r=L;for (int i=0;i<10;i++){s=(struct List*)malloc(sizeof(struct List));s->data=i;r->next=s;r=s;}r->next=NULL;}void DisPlay(List *L){List *p=L->next;while(p!=NULL){printf ("%d ",p->data);p=p->next;}printf("\n");}int main (){List *L1,*L2;L1=(struct List*)malloc(sizeof(struct List));L2=(struct List*)malloc(sizeof(struct List)); HeadCreatList(L1);DisPlay(L1);TailCreatList(L2);DisPlay(L2);}//头插法创建链表#include <stdio.h>#include <stdlib.h>struct node{int data;struct node * next;};//建立只含头结点的空链表struct node * create_list(){struct node * head = NULL;head = (struct node *)malloc(sizeof(struct node));if (NULL == head){printf("memory out of use/n");return NULL;}head->next = NULL;head->data = 0;return head;}//头插法建立链表int insert_form_head(struct node * head, int num){struct node * head_t = head->next;struct node * new_node = NULL;new_node = (struct node *)malloc(sizeof(struct node));if (NULL == new_node){printf("memory out of use/n");return -1;}//将新结点插入到链表的最后new_node->data = num;new_node->next = head_t;head->next = new_node;return 0;}//打印链表int show_list(struct node * head){struct node * temp;temp = head->next;while(temp){printf("%d/n",temp->data);temp = temp->next;}return 0;}// 按值删除结点，头结点不被删除int delete_node(struct node *head, int data){//head_t 保存要删除结点的上一个结点struct node * head_t = head;struct node * temp = NULL;if (head == NULL){printf("delete node from empty list!/n");return -1;}//查找删除的结点的前一个结点//如果此处查找的是删除的结点，则需要另加一个指针保存删除结点的前一个指针while(NULL != head_t->next){if (data == head_t->next->data)break;head_t = head_t->next;}//如果要删除的结点不存在，直接返回if (NULL==head_t->next){printf("node not found/n");return -1;}//删除操作temp = head_t->next;head_t->next = head_t->next->next;free(temp);return 0;}void main(int argc, char* argv[]){struct node * head;head = create_list();if (NULL == head)printf("create_list error/n");insert_form_head(head,123);insert_form_head(head,456);show_list(head);printf("delete once!/n");delete_node(head,123);show_list(head);printf("delete second!/n");delete_node(head,456);show_list(head);delete_node(head,0);show_list(head);}/*//尾插法创建链表#include<stdio.h>#include<stdlib.h>struct Node{int data;struct Node * next;};//建立只含头结点的空链表struct Node * create_list(){struct Node * head = NULL;head = (struct Node *)malloc(sizeof(struct Node));if (NULL == head){printf("memory out of use/n");return NULL;}head->next = NULL;head->data = 0;return head;//尾插法建立链表int insert_form_tail(struct Node * head, int num){struct Node * temp = head;struct Node * new_node = NULL;new_node = (struct Node *)malloc(sizeof(struct Node));if (NULL == new_node){printf("memory out of use/n");return -1;}//寻找尾结点while (temp->next != NULL){temp = temp->next;}//将新结点插入到链表的最后new_node->data = num;new_node->next = NULL;temp->next = new_node;return 0;}//打印链表int show_list(struct Node * head){struct Node * temp;temp = head->next;while(temp){printf("%d/n",temp->data);temp = temp->next;}return 0;}void main(int argc, char* argv[]){struct Node * head;head = create_list();if (NULL == head)printf("create_list error/n");insert_form_tail(head,123);insert_form_tail(head,456);show_list(head);*/。

C实现头插法和尾插法来构建单链表（不带头结点）链表的构建事实上也就是不断插⼊节点的过程。

⽽节点的插⼊能够分为头插法和尾插法。

//// main.c// HeadInsertAndTailInsert//// Created by chenyufeng on 16/2/25.// Copyright © 2016年 chenyufengweb. All rights reserved.///*** 分别使⽤头插法和尾插法建⽴单链表*/#include <stdio.h>#include "stdlib.h"#include "string.h"typedef int elemType;//构造节点typedef struct ListNode{int element;struct ListNode *next;}Node;//初始化链表void initList(Node *pNode){pNode = NULL;printf("%s函数运⾏，头结点初始化完毕\n",__FUNCTION__);}//打印链表void printList(Node *pNode){if (pNode == NULL) {printf("%s函数运⾏，链表为空，打印失败\n",__FUNCTION__);}else{while (pNode != NULL) {printf("%d ",pNode->element);pNode = pNode->next;}printf("\n");}}//头插法Node *HeadInsert(Node *pNode){Node *pInsert;pInsert = (Node*)malloc(sizeof(Node));if (pInsert == NULL) {printf("%s函数运⾏。

第1章绪论习题一、问答题1. 什么是数据结构?2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中,类的作用是什么?9. 参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言(如C、或PASCAL)中,指针类型是原子类型。

三、计算下列程序段中XX1 的语句频度fori1iltni forj1jltij fork1kltjk xx1 提示: i1 时:1 11×1/2 112/2 i2 时:12 12×2/2 222/2 i3 时:123 13×3/2 332/2 … in 时:123……n 1n×n/2 nn2/2 fn 123……n 12 22 32 …… n2 / 2 1nn/2 nn12n1/6 / 2 nn1n2/6 n3/6n2/2n/3区分语句频度和算法复杂度:Ofn On3 四、试编写算法求一元多项式Pnxa0a1xa2x2a3x3…anxn 的值Pnx0,并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。

注意:本题中的输入aii01…n x 和n,输出为Pnx0.通常算法的输入和输出可采用下列两种方式之一:(1)通过参数表中的参数显式传递;(2)通过全局变量隐式传递。

试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。

提示:floatPolyValuefloat a float x int n…… 核心语句:p1 x 的零次幂s0 i 从0 到n 循环ssaip ppx 或:px x 的一次幂sa0 i 从1 到n 循环ssaip ppx 实习题设计实现抽象数据类型“有理数”。

建⽴链表—头插法、尾插法—有⽆头结点1.建⽴链表-头插法-头结点1//建⽴链表-头插法-头结点2 LinkList CreatList_head()3 {4 DataType x; //数据5 LinkList p,head; //结点6 head = (LinkList)malloc(sizeof(LNode));7 head->next = NULL;8 head->data = 0;910 scanf("%d",&x);11while(x != 999)12 {13 p = (LinkList)malloc(sizeof(LNode));14 p->data = x; //存数据15 p->next = head->next;16 head->next = p;17 head->data++; //结点计数18 scanf("%d",&x);19 }20return head;21 }2223//输出链表-头插法-头结点24void PrintList_head(LinkList p)25 {26 LinkList a;27 a = p->next;28while(a != NULL)29 {30 printf("%d ",a->data);31 a = a->next;32 }33 printf("\n");34 }2.建⽴链表-头插法-⽆头结点1//建⽴链表-头插法-⽆头结点2 LinkList CreatList()3 {4 DataType x;5 LinkList p,head;6 head = NULL;78 scanf("%d",&x);9while(x != 999)10 {11 p = (LinkList)malloc(sizeof(LNode));12 p->data = x;13if(head == NULL)14 { head = p;15 p->next = NULL;16 }17else18 {19 p->next = head;20 head = p;21 }22 scanf("%d",&x);23 }24return head;25 }262728//输出链表-头插法-⽆头结点29void PrintList(LinkList p)30 {31 LinkList a;32 a = p;33while(a != NULL)34 {35 printf("%d ",a->data);36 a = a->next;37 }38 printf("\n");39 }3.建⽴链表-尾插法-⽆头结点 1//建⽴链表-头插法-⽆头结点2 LinkList CCC()3 {4 DataType x;5 LinkList p,head;6 head = NULL;78 scanf("%d",&x);9while(x != 999)10 {11 p = (LinkList)malloc(sizeof(LNode));12 p->data = x;13 p->next = head;14 head = p;1516 scanf("%d",&x);17 }18return head;19 }202122//输出链表-头插法-⽆头结点23void PPP(LinkList p)24 {25 LinkList a;26 a = p;27while(a != NULL)28 {29 printf("%d ",a->data);30 a = a->next;31 }32 printf("\n");33 }4.建⽴链表-尾插法-头结点 1//建⽴链表-尾插法-头结点2 LinkList Tailhead()3 {4 DataType x;5 LinkList p,head,r;6 head = (LinkList)malloc(sizeof(LNode));7 head->next = NULL;8 r = head;9 scanf("%d",&x);10while(x != 999)11 {12 p = (LinkList)malloc(sizeof(LNode));13 p->data = x;14 p->next = r->next;15 r->next = p;16 r = p;17 scanf("%d",&x);18 }1920return head;21 }22//输出链表-尾插法-头结点23void PrintTailhead(LinkList p)24 {25 LinkList a;26 a = p->next;27while(a != NULL)28 {29 printf("%d ",a->data);30 a = a->next;31 }32 printf("\n");33 }。

链式存储（头插法、尾插法）#include "stdio.h"#include "string.h"#include "ctype.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 // 存储空间初始分配量typedef int Status;// Status是函数的类型,其值是函数结果状态代码。

如OK等typedef int ElemType;//ElemType类型依据实际情况⽽定，这⾥如果为intStatus visit(ElemType c){printf("%d ",c);return OK;}typedef struct Node{ElemType data;struct Node *next;}Node;typedef struct Node *LinkList; // 定义LinkList// 初始化顺序线性表Status InitList(LinkList *L){*L=(LinkList)malloc(sizeof(Node)); // 产⽣头结点,并使L指向此头结点if(!(*L)) // 存储分配失败return ERROR;(*L)->next=NULL; //指针域为空return OK;}//初始条件：顺序线性表L已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSEStatus ListEmpty(LinkList L){if(L->next)return FALSE;elsereturn TRUE;}// 初始条件：顺序线性表L已存在。

东莞理工学院（本科）试卷（A 卷）2006 -2007 学年第二学期开课单位：软件学院，考试形式：闭卷，允许带入场科目：数据结构与算法分析班级：姓名：学号：一、填空题（每小题2分，共18分）1、对于给定的n个元素,可以构造出的逻辑结构有集合, ，和四种。

2、数据结构中评价算法的两个重要指标是和。

3、数据类型指的是和定义在的总称。

4、顺序存储结构是通过表示数据元素之间的(逻辑)关系；链式存储结构是通过表示数据元素之间的(逻辑)关系。

5、栈是的线性表，其操作数据的基本原则是。

6、设有一个二维数组A[0…9][0…9]，若每个元素占3个基本存储单元，A[0][0]的地址是600，若按行优先（以行为主）顺序存储，则A[6][8]的存储地址是。

7、树的先序遍历实质上与将树转换成二叉树后对二叉树的相同；而树的后序遍历实质上与将树转换成二叉树后对二叉树的相同。

8、若采用邻接矩阵存储一个图所需要的存储单元取决于图的；无向图的邻接矩阵一定是。

9、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、有算法sum(n)，其时间复杂度是（ A ）。

sum( int n ){ int sum=0, m, t ;for (m=1; m<=n; m++){ p=1 ;for (t=1; t<=m; t++) p*=t ;sum+=p ;}return (sum) ;}（A）O(n2) （B）O(m2) （C）O(m+n) （D）O(n×m)2、设p是非空单链表中结点q的直接前驱结点，删除q的正确操作是（ B ）。

（A）p->next=q->next；free(p) ; （B）p->next= q->next；free(q) ;（C）q->next=p->next；free(p) ; （D）q->next=p->next；free(q) ;3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ D ）。

实验一链表的建立及基本操作方法实现一、【实验目的】1、理解和掌握单链表的类型定义方法和结点生成方法。

2、掌握利用头插法和尾插法建立单链表和显示单链表元素的算法。

3、掌握单链表的查找（按序号）算法。

4、掌握单链表的插入、删除算法。

二、【实验内容】1、利用头插法和尾插法建立一个无头结点单链表，并从屏幕显示单链表元素列表。

2、利用头插法和尾插法建立一个有头结点单链表，并从屏幕显示单链表元素列表。

3、将测试数据结果用截图的方式粘贴在程序代码后面。

重点和难点：尾插法和头插法建立单链表的区别。

建立带头结点和无头结点单链表的区别。

带头结点和无头结点单链表元素显示方法的区别三、【算法思想】1) 利用头插法和尾插法建立一个无头结点单链表链表无头结点，则在创建链表时，初始化链表指针L=NULL。

当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给L,新结点next指向空，即L=p,p->next=NULL，若表中已经有元素了，则将新结点的next指向首结点，然后将新结点赋给L即（p->next=L,L=p）。

当用尾插法插入元素时，首先设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer和头指针一样即tailPointer=L。

插入元素时，首先判断链表是否为空，若为空，则直接将新结点赋给L即L=p，若不为空，else将最后一个元素的next指向新结点即tailPointer->next=p，然后跳出这个if,else语句，将新结点next指向空，并且将tailPointer指向新结点即p->next=NULL,tailPointer=p。

2) 利用头插法和尾插法建立一个有头结点单链表链表有头结点，则在创建链表时，初始化链表指针L->next = NULL。

与无头结点区别在于，判断链表为空是根据L->next是否为空。

用头插法插入元素时，要判断链表是否为空，若为空则将新结点next指向空，作为表尾，若不为空，则直接插入，将新结点next指向头结点next的指向，再将头结点next指向新结点即p->next=L->next,L->next=p。