数据结构以及C语言常问与难点
数据结构以及C语言常问与难点
1.序言
2.常问与难点，为避免重复发帖，特设此帖并置顶，以供浏览查阅。
3.内容主要是将本版的好帖子收集起来，并加以整理，仅给出知识点分析与问题解答，并不给出原帖链接，致歉。
4.本版中的好东西会慢慢添加进来（各位版主齐心协力，每天添加一个知识点，用不了多久就会很强大），本帖观点只
是各位版主和我个人的分析，不一定尽善尽美，但一定是尽心尽力。各位热心研友如有修正和补充，请在回复中说明。
5.特代表研友感谢各位版主的辛勤奉献，代表版主感谢热心研友对王道的支持（呵呵）。特别地，祝备考10的研友们一
切顺利，考上理想的学校。珍惜时间，努力才是王道。
1.目录，共占用一个代码区
2.
3. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。
4.typedef struct LNode{
5. ElemType data;
6. struct LNode *next;
7.} LNode, *LinkList;
8.
9. 2.符号&的含义，指针进阶。涉及知识点：引用机制，实参与形参，C语言中地址与指针（以及指向指针的指针），指
针的传递（暂不涉及数组与指针的知识，将在以后介绍）。
10.
11. 3.如下方式动态分配内存的全部细节解释。涉及知识点：动态分配内存，define，强制类型转换，malloc()，顺序
表存储结构，顺序表与数组，链表结点的内存分配，指针细节，附完整程序。
12.L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
复制代码
1.正文，每个问题占用一个代码区
复制代码
1. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。
2.typedef struct LNode{
3. ElemType data;
4. struct LNode *next;
5.} LNode, *LinkList;
6.
7.如下是一个最简单的结构体定义：
8.struct Node{
9. int x,y;
10.};
11.最后一个分号是不能丢掉的。这样，上述结构体定义的核心就是
12.struct LNode{
13. ElemType data;
14. struct LNode *next;
15.};
16.先说ElemType，它并不被编译器识别，完全COPY到程序里肯定是不能执行的。实际上这只是严书伪代码与读者的一
个约定，指元素类型。在实际编程中，如果我们在程序开头写到 typedef int ElemType; 那我们在程序后面就可以直接使用 ElemType data; 其作用和 int data; 是一样的。
17.typedef相当于我们与编译器的一个约定(windows编程内置了很多这样的约定，只是为了使类型名称更易识记)，后
面还会有一点关于typedef的解释，如有必要请参阅C语言课本。
18.struct LNode *next;指向本类型的指针，通常在链表中指向另一个结点，在树中指向子树，在图中指向邻结点，等
等。我这样说只是让你能更容易理解指针的作用。其细节与变化稍后解释。
19.
20.这样，其核心已经理解了，下面就用struct{}来代替核心部分。原结构体定义写成如下形式：
21.typedef struct{} LNode, *LinkList;
22.这是不是和 typedef int ElemType; 很像，至少有半句 typedef struct{} LNode; 是一样的，其作用正如上
文所说，其使用效果稍后提到。现在我们关心另外半句 typedef struct{} *LinkList; 请看简单的例子，如下：
23.typedef int *Pointer;
24.实际编程时，定义一个指针，Pointer xx; 与int* xx; 的作用是一样的。这样就不难理解typedef struct{}
*LinkList; 了，这里需要注意的是LNode与LinkList的名称是不能一样的。
25.
26.下面是完整的程序以说明结构体如何定义与如何使用，及其变化。
27.#include//************************************************begin
28.#include
29.
30.typedef int ElemType;
31.
32.typedef struct node{
33. ElemType data;
34. struct node *next;
35.} LNode, *LinkList;
36.
37.//细心的你可能已经发现，此处我做了更改，将 struct 后面的 LNode 变成了node
38.//此处的 node 须与大括号中的struct node *next; 中的node一致，
39.//node 与大括号后面的LNode 无需一致，这是因为typedef的作用
40.
41.//struct node *next; 中的 struct node 不能用LNode 代替，因为编译器
42.//检查到 struct node *next; 时还并不知道有 LNode 这个东西。
43.
44.int main()
45.{
46. LNode exp1;
47. struct node exp2;
48. //这是两种方式是一样的
49.
50. exp1.data=100;
51. exp2.data=200;
52.
53. LinkList exp3;
54. LNode *exp4;
55. struct node *exp5;
56. //这三种方式是一样的
57.
58. exp3=(LinkList)malloc(sizeof(LNode));
59. exp4=(LNode*)malloc(sizeof(LNode));
60. exp5=(struct node*)malloc(sizeof(struct node));
61. //为结点分配内存，这一点很重要，以后会作解释
62. //这三种写法是一样的
63.
64. exp3->data=300;
65. exp4->data=400;
66. exp5->data=500;
67. //注意这里是“->”，而不是“.”
68.
69. exp3->next=exp4;
70. exp4->next=exp5;
71. exp5->next=NULL;
72. //单链表，末尾指针要置空，这一点也很重要
73.
74. return 0;
75.}//***********************************************************end
76.
77.呵呵，还有一个小经验。
78.typedef struct {
79. ElemType data;
80.} LNode, *LinkList;
81.省略 struct 后面的结构体名称也是可以的，但前提是大括号中不能有指向本类型的指针，至于为什么我就不说啦。
对于比较懒的我可以少打一个单词呢，嘿嘿，这个意义太重大了。
复制代码
1. 2.符号&的含义，指针进阶。涉及知识点：引用机制，实参与形参，C语言中地址与指针（以及指向指针的指针），指
针的传递（暂不涉及数组与指针的知识，将在以后介绍）。
2.
3.（1）引用机制
4.严书里经常看到&，C语言里是地址符，卡住了很多初学者。对于理解伪代码，把符号&当做C++中的引用符就可以了。
通过下面的例子对引用机制做简单解释。
5.void f_exp(int &x, int y)
6.{ x=100;y=100;
7.}
8.int main()
9.{ int a=200,b=200;
10. f_exp(a,b);
11. printf("%d %d\n",a,b);
12. return 0;
13.}
14.程序输出 100 200 ，这就是符号&在引用机制中的作用。
15.
16.（2）形参与实参
17.对于函数f_exp()来说，变量x,y都是形参，他们在函数执行完就被释放了，他们的值也就不存在了，x,y可以是任
意符合变量命名规则的名称(即使是a和b)来代替，并不影响函数f_exp()的功能。这对理解指针的传递是有帮助的。
而实参是a和b，他们将值传递给函数f_exp()就完成任务了（如果此处没有使用引用），f_exp()只是接收了a和b 的值，完成一定的功能（可能要返回一些值），这样，实参b并没有被改变，而实参a由于引用机制，在函数f_exp()执行过程中被重新赋值。
18.
19.（3）地址和指针
20.请看这个简单的例子：
21.int main()
22.{ int a=1;
23. int *p;
24. p=&a;
25. printf("%d %d\n",a,&a);
26. printf("%d %d\n",*p,p);
27. return 0;
28.}
29.此处的&是地址符，a是整型变量，其值是1，&a是a的地址，用整型来输出。
30.这里，p是一个指针，p指向变量a，故*p的值是1。而p本身的值是什么呢？
31.通过程序输出我们可以看到，p本身实际上存储的就是a的地址，整形输出&a和p的值是一样的。
32.
33.现在让我们来更进一步：
34.int main()
35.{ int a=1;
36. int *p;
37. int **q;
38. p=&a;
39. q=&p;
40. printf("%d %d %d\n",&p,p,a);
41. printf("%d %d %d\n",q,*q,**q);
42. return 0;
43.}
44.呵呵，我自己都有点乱了，不要怕，听我慢慢道来。p是指向变量a的指针，q是指向变量p(我们把指针也当成一个
变量，在上一例中我们知道指针p这个变量存储的值是a的地址)的指针，是不是清晰一点了。上例中我们知道了变量(指针)p的值，那变量(指针)p的地址又是多少呢？从程序输出中我们可以发现，它就是指针q本身所存储的值，更深入一些，我们还可以知道指针q的地址。
45.另外一点，**q,*p,a它们三个的值是一样的，你想明白了吗？
46.这个一定要搞明白，明白了这个，指针就明白一半了，下面要讲的指针传递，以后要讲的数组与指针，动态分配数组，
就不是那么难理解了。
47.
48.（4）指针传递通常与数组联系在一块的，我恐怕越讲越复杂，暂不讲数组，但这样让我很难做啊。请看下面这个简单
例子：
49.void f_exp(int *x,int y)
50.{ *x=100;y=100;
51.}
52.int main()
53.{ int a=200,b=200;
54. int *p;
55. p=&a;
56. f_exp(p,b);
57. printf("%d %d\n",a,b);
58. return 0;
59.}
60.这个输出与上面引用机制的输出是一样的，但函数f_exp()的第一个参数是指针，其原理如下所述：
61.调用f_exp(p,b)时，这里只讨论第一个参数，传给函数的实际值是p的值，也就是a的地址，注意：函数执行过程
中x的值是a的地址，而我们不去管程序是如何存储x的（因为存储X的这个位置在函数结束后被释放掉了），我们只关心x的值，它是a的地址，我们使用*x=100（而不是使用x本身），有没有发现*x和*p此刻在共用同一地址，指向同一个变量a，所以变量a的值被改变了。然后我提一个小小的问题，如果在函数中对指针x的值做了改变，如x 指向了另一个变量，那么p的值会不会改变呢？请认真思考一下，因为这在以后的一个问题中会用到。
62.这就是C语言中指针的巧妙之处，它巧妙的把地址传到函数之中，然后对该地址的变量做改变。虽然巧妙，但很复杂，
稍不注意便会出错。这也正是C++中引入引用机制的原因，一个符号&就解决了这个问题。当然这并不能说明指针是多
余的，因为指针的巧妙与灵活还是有很多用武之地的。
63.因为是地址的传递，所以有时候把引用符号&当作地址符貌似也能理解引用机制，但请你别这样做，因为这种理解方式
有时候是不可行的，仅管我现在举不出具体的例子来。
64.我自认为已经写的很清楚了，如果还不甚了然请看看C语言课本。搞懂这些不是一件容易的事情，但我先恭喜你你对
指针的理解又更进一步。更复杂一些的与数据结构联系更紧密的指针传递，我将在讲完为结点动态分配内存后讲到。复制代码
1. 3.如下方式动态分配内存的全部细节解释。涉及知识点：动态分配内存，define，强制类型转换，顺序表存储结构，
顺序表与数组，链表结点的内存分配，指针细节，附完整程序。
2.L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
3.
4.这一句代码出现在严书P23页算法2.3中，有必要将P22页顺序表结构体定义中涉及本节的部分写在下面：
5.#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
6.typedef struct {
7. ElemType *elem; //存储空间基址
8. int length;
9. int listsize;
10.}SqList;
11.
12.（1）先分别解释每一部分的含义：
13.
14.#define LIST_INIT_SIZE 100的作用，简言之，编译器在预编译的时候会把程序中出现的所有LIST_INIT_SIZE
机械地替换为100，如果这样还有所疑惑，请参阅C语言课本。
15.
16.(ElemType*)是强制类型转换，有关ElemType前文已经讲过，而ElemType*类型是什么呢？
17.当我们定义一个整型变量时我们使用
18.int a;
19.而当我们定义一个指向整型变量的指针时我们使用
20.int *a;
21.实际上，int *类型可以理解为一个指向整型的指针变量。那ElemType*类型就不用我多说了吧。
22.
23.malloc()函数，往往是卡住初学者的又一个地方。C语言来说，malloc()函数包含在stdlib.h这个头文件中，也就
是说，使用malloc()必须在程序开头写上#include
存空间，并返回其首址。
24.
25.sizeof()函数，正如它的名字一样，sizeof(ElemType)就是ElemType这种数据类型的大小，也就是一个ElemType
变量所占用的字节数，可以写个简单的程序看看sizeof(int),sizeof(float),sizeof(double)的值是什么，不同的编译器和操作系统得到的结果可能不一样。但这是系统内部实现的问题，在此处我们不需要关心，
100*sizeof(ElemType)我们直观的理解为100个ElemType类型元素所需要的空间大小，单位是字节。
26.
27.从本例来讲，L.elem是个ElemType*的变量（一个指向ElemType类型的指针)，malloc()分配了
100*sizeof(ElemType)大小的连续的内存空间，其首地址被强制转换成ElemType*类型，然后赋给了L.elem。
28.
29.（2）顺序表存储结构，顺序表与数组。
30.我们估且不去管这块内存空间到底在内存的什么地方，我们唯一能找到它的办法就是L.elem这个指针，而且这块内
存必须是连续的，大小是在分配的时候指定，之后不能再更改。L.elem指向第1个元素，L.elem+1指向第二个元素...
我们想访问第N个元素，系统可以直接计算出第N个元素的内存地址，L.elem+(N-1)*sizeof(ElemType)。这样的一块内存，实际上就是顺序表，是一种存储结构，上述的访问方式也就是所谓的可以随机访问。
31.
32.而事实上，这也正是数组的实现方式。当我们使用int a[100];来定义一个数组时，系统分配100*sizeof(int)的
连续内存空间，并把首地址赋给a，此时我们可以把a当作一个指针来使用，我们使用a[0]和*a的效果是一样，而a[1]和*(a+1)是一样的。请看下例：
33.
34.int a[10];//静态分配，分配内存的工作由系统完成
35.int* a_dx;//动态分配大小是10个int型的连续内存，首址赋给指针a_dx，内存一旦分配，大小不便改变。
36.a_dx=(int*)malloc(sizeof(int)*10);
37.
38.（3）链表结点的内存分配。
39.请看下面的例子，我首先强调这个例子不是正确的，不过你可以亲自在VC++6.0上调试一下。
40.#include
41.#include
42.typedef struct node
43.{
44. int data;
45. struct node* next;
46.} exp, *lexp;
47.int main()
48.{
49. lexp List;
50. printf("%d\n",List->data);
51. return 0;
52.}
53.程序的内容简单不过，有不懂的地方在本帖上文均有解释。编译器给出如下信息：
54. warning C4700: local variable 'List' used without having been initialized
55.变量"List”未被初始化，也就是对于系统来说，你只是定义了一个指针List，它有一个默认的初值，就像int a;一
样，a也会有一个默认的初值，不同的系统和编译器这个值可能不一样，但糟糕的是，指针List未被初始化，它指向了内存中一个未知的地方，我试着执行程序的时候，其实我的心在颤抖，我十分担心系统崩溃，我并不是没有遇到过这样的情况。这其实和数组越界是一个道理，指针指向了未知的地方，有了未知的危险，但通常只是程序无法继续执行罢了，所以不用太担心。
56.
57.我们在lexp List;这句话后面添加一句：
58. List=(lexp)malloc(sizeof(exp));
59.它实际上是分配了一块内存空间，把首址赋给List，一会来解释为何是首址。这样，指针List有了明确的指向，编
译器不会再给出warning，细心的同学可能已经注意到，此时对List所指结点中的data变量，即List->data，我们并没有对它进行初始化，我们输出它的值是系统默认的初值，但这似乎并没有什么危险，所以编译器并未给出warning。实际上似乎是程序员忘记了对List->data赋值，仅管这种错误可能对程序的结果产生影响，但编译器已经帮我们做了所有能做的，它不是万能的，还是要程序员细心，有良好的编程习惯和风格。
60.
61.以上过程就是为链表分配一个结点了，现在来解释 List=(lexp)malloc(sizeof(exp));为何是首址赋给了List。
先看下例：
62.#include
63.#include
64.int main()
65.{
66. printf("%d %d\n",sizeof(int),sizeof(double));
67.
68. int a[10];
69. printf("%d\n",a+1);
70. printf("%d\n",a);
71. printf("%d\n",&a[1]-&a[0]);
72. printf("%d\n",(int)&a[1]-(int)&a[0]);
73.
74. double b[10];
75. printf("%d\n",b+1);
76. printf("%d\n",b);
77. printf("%d\n",&b[1]-&b[0]);
78. printf("%d\n",(int)&b[1]-(int)&b[0]);
79.
80. return 0;
81.}
82.请在VC++6.0中运行上述程序，观察并分析输出结果，你可能已经发现了什么。使用一个指针a和a+1时，系统会自
动根据指针a的类型来找到其下一项a+1，这也是a[1]a[0]的地址的差与b[1]b[0]的地址的差不一样的原因。
83.
84.现在，我们来分析,假设a的值是16，即a[0]的地址是16，a+1的值是20，因为这是一个整型数组，每一个int型
数据占用4个字节，实际上，内存16，17，18，19这4个字节用来存储a[0]，但a[0]的地址值是16，请仔细想一下，系统根据a的类型（整型）和a的值(16)，就可以知道内存16，17，18，19这4个字节存储的就是a[0]，如果对这4个字节的内容继续深究，我们还可以知道此系统此编译器下数据是高位存储还是低位存储，这要用到位操作的知识，有兴趣可以自己研究一下。
85.
86.同样，对于一个自定义的数据结构类型，如上文的exp类型，为一个此类型的结点动态分配内存，只是把首址赋给某
指针，然后系统根据该指针的类型和该指针的值，可以计算出内存中哪些字节用来存储此结点，根据结构内各个成员的大小和顺序，也可以计算出每个成员在内存中的位置。
87.
88.我解释这些只是为了让你对指针的工作原理有更进一步的理解，实际上这有些多余，因为这些反应到程序员编程时，
我们只需要简单的以List->data的形式就可以找到结点并调用结点的任何成员，前提是我们为这个结点分配了内存。复制代码
数据结构(c语言版)复习资料
数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
数据结构C语言版期末考试试题(有答案)
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均
数据结构C语言第三版习题5参考答案
习题5参考答案 5.1 选择 （1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C（16）B 5.2 填空 （1）1 （2）1036；1040 （3）2i （4） 1 ； n ; n-1 ; 2 （5）2k-1；2k-1 （6）ACDBGJKIHFE （7）p->lchild==NULLL （8）Huffman树 （9）其第一个孩子; 下一个兄弟 （10）先序遍历；中序遍历 5.3 叶子结点:C、F、G、L、I、M、K； 非终端结点：A、B、D、E、J； 各结点的度： 结点： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0 树深：4 5.4 无序树形态如下： 二叉树形态如下：
5.5 二叉链表如下: 三叉链表如下: 5.6 先序遍历序列:ABDEHICFJG
中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA 5.7 (1) 先序序列和中序序列相同：空树或缺左子树的单支树； (2) 后序序列和中序序列相同：空树或缺右子树的单支树； (3) 先序序列和后序序列相同：空树或只有根结点的二叉树。 5.8 这棵二叉树为: 5.9 先根遍历序列:ABFGLCDIEJMK 后根遍历序列:FGLBCIDMJKEA 层次遍历序列:ABCDEFGLIJKM 5.10 证明：设树中结点总数为n，叶子结点数为n0，则 n=n0 + n1 + …… + n m （1） 再设树中分支数目为B，则 B=n1 + 2n2 + 3n3+ …… + m n m （2） 因为除根结点外，每个结点均对应一个进入它的分支，所以有 n= B + 1 （3） 将（1）和（2）代入（3），得 n0 + n1 + …… + n m = n1 + 2n2 + 3n3+ …… + m n m + 1 从而可得叶子结点数为： n0 = n2 + 2n3+ …… + (m-1)n m + 1 5.11 由5.10结论得，n0 = (k-1)n k + 1 又由 n=n0 + n k，得n k= n-n0，代入上式，得 n0 = (k-1)（n-n0）+ 1 叶子结点数为：n0 = n (k-1) / k
数据结构c语言版试题大全含答案
1 绪论沈阳理工大学应用技术学院信息与控制学院 计算机科学与技术教研室 2011-5-8
数据结构复习题：绪论 单选题 1、在数据结构中，与所使用的计算机无关的数据叫_____结构。 A存储|B物理|C逻辑|D物理和存储 2、在数据结构中，从逻辑上可以把数据结构分成______。 A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图 3、数据结构在计算机内存中的表示是指_______。 数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的______结构。 逻辑|存储|逻辑和存储|物理 5、在以下的叙述中，正确的是_____。 线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出 6、在决定选取何种存储结构时，一般不考虑_______。 各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 8、下面说法错误的是_______。 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3)所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界 (4)同一个算法，实现语句的级别越高，执行效率越低 (1)|(1)、(2)|(1)、(4)|(3) 9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着______。 数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等 10、以下说法正确的是_______。 数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构 11、____是数据的最小单元,_____是数据的基本单位. 数据项|数据元素|信息项|表元素 12、数据结构是指_____以及它们之间的_____. (1)数据元素(2)结构|(1)计算方法(2)关系|(1)逻辑存储(2)运算|(1)数据映像(2)算法 13、计算机所处理的数据一般具备某种内在的关系,这是的指_____. 数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系 14、数据的逻辑结构可以分为_____两类. 动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构 15、数据的逻辑结构是指_____关系的整体. 数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间 16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____. 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法
数据结构(c语言版)期末考试复习试题
《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位
B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);} 数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i 《数据结构与算法》复习题 一、选择题。 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时，一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ，算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 目录 第1章绪论............................................. 错误!未定义书签。第2章线性表........................................... 错误!未定义书签。第3章栈和队列......................................... 错误!未定义书签。第4章串、数组和广义表................................. 错误!未定义书签。第5章树和二叉树....................................... 错误!未定义书签。第6章图................................................ 错误!未定义书签。第7章查找............................................. 错误!未定义书签。第8章排序............................................. 错误!未定义书签。 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 数据结构C语言版第2版课后习题答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 目录 第1章绪论 ............................................................................ 错误!未定义书签。第2章线性表......................................................................... 错误!未定义书签。第3章栈和队列 ..................................................................... 错误!未定义书签。第4章串、数组和广义表 ........................................................ 错误!未定义书签。第5章树和二叉树 .................................................................. 错误!未定义书签。第6章图 ................................................................................ 错误!未定义书签。第7章查找 ............................................................................ 错误!未定义书签。第8章排序 ............................................................................ 错误!未定义书签。 I 人生难得几回搏，此时不搏更待何时？ 第1章绪论 1.1 简述下列术语：数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解：数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解：抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中 试按图论中图的画法惯例画出其逻辑结构图 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数） 解： ADT Complex{ 数据对象：D={r i|r i为实数} 数据关系：R={ 数据结构C语言版第一 二章习题答案 Document number：BGCG-0857-BTDO-0089-2022 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题 （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．栈6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100;? while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 不管怎样，生活还是要继续向前走去。有的时候伤害和失败不见得是一件坏事，它会让你变得更好，孤单和失落亦是如此。每件事到最后一定会变成一件好事，只要你能够走到最后。附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B. C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体 是计算机程序加工和处理的对象 包括数值数据和非数值数据 数据项：数据项指不可分割的、具有独立意义的最小数据单位 数据项有时也称为字段或域 数据元素：数据元素是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系 数据类型：是指变量的取值范围和所能够进行的操作的总和 算法：是对特定问题求解步骤的一种描述 是指令的有限序列 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 第1章绪论 5．选择题：CCBDCA 6．试分析下面各程序段的时间复杂度。 （1）O（1） （2）O（m*n） （3）O（n2） （4）O（log3n） （5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2） （6）O(n) 第2章线性表 1．选择题 babadbcabdcddac 2．算法设计题 （6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; （7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } } （10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 [题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。 void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i 《数据结构》 第五版 清华大学自动化系 李宛洲 2004年5月 目录 第一章数据结构--概念与基本类型 (6) 1.1概述 (6) 1.1.1数据结构应用对象 (6) 1.1.2学习数据结构的基础 (7) 1.1.2.1 C语言中的结构体 (7) 1.1.2.2 C语言的指针在数据结构中的关联作用 (8) 1.1.2.3 C语言的共用体(union)数据类型 (12) 1.1.3数据结构定义 (15) 1.2线性表 (17) 1.2.1 顺序表 (18) 1.2.2 链表 (20) 1.2.2.1链表的基本结构及概念 (20) 1.2.2.2单链表设计 (22) 1.2.2.3单链表操作效率 (29) 1.2.2.4双链表设计 (30) 1.2.2.5链表深入学习 (32) 1.2.2.6稀疏矩阵的三元组与十字链表 (36) 1.2.3 堆栈 (41) 1.2.3.1堆栈结构 (41) 1.2.3.2基本操作 (42) 1.2.3.3堆栈与递归 (44) 1.2.3.4递归与分治算法 (45) 1.2.3.5递归与递推 (49) 1.2.3.6栈应用 (52) 1.2.4 队列 (57) 1.2.4.1队列结构 (57) 1.2.3.2队列应用 (59) 1.3非线性数据结构--树 (64) 1.3.1 概念与术语 (64) 1.3.1.1引入非线性数据结构的目的 (64) 1.3.1.2树的定义与术语 (65) 1.3.1.3树的内部节点与叶子节点存储结构问题 (66) 1.3.2 二叉树 (66) 1.3.2.1二叉树基本概念 (66) 1.3.2.2完全二叉树的顺序存储结构 (68) 1.3.2.3二叉树遍历 (69) 1.3.2.4二叉树唯一性问题 (71) 一、单项选择 1 . 数据在计算机内有链式和顺序两种存储方 式，在存储空间使用的灵活性上，连式存储比顺序存 储要 A . 低 B . 高 C . 相同 D . 不好说 2 . 通常对数组进行的两种基本操作是（） A . 建立与删除 B . 索引和修改 C . 查找和修改 D . 查找与索引 3 . 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F 中结点的（）。 A . 中序 B . 前序 C . 层次序 D . 后序 4 . 由树的定义，具有3个结点的树有（）种形态 A . 2 B . 3 C . 4 D . 5 5 . 以下说法错误的是 ( ) A . 二叉树可以是空集 B . 二叉树的任一结点都有 两棵子树 C . 二叉树与树具有相同的 树形结构 D . 二叉树中任一结点的两 棵子树有次序之分 6 . 若节点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 A . 顺序存储结构 B . 链式存储结构 C . 索引存储结构 D . 散列存储结构 7 . 已知二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（） A . bdgcefha B . gdbecfha C . bdgaechf D . gdbehfca 8 . 算法分析的两个主要方面 A . 空间复杂度和时间复杂 度 B . 正确性和简明性 C . 可读性和文档性 D . 数据复杂性和程序复杂 性 9 . 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。 (A) 6 (B) 11 (C) 5 (D) 6.5 A . B . C . D . 10 . 若邻接表中有奇数个表节点，则一定（ ） A . 图中有奇数个顶点 B . 图中有偶数个顶点 C . 图为无向图 D . 图为有向图 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 专业 《数据结构（C 语言描述）》期末试卷 （ — 学年 第 学期） 一、填空(10分) 1、一个m 阶B-树中，每个结点最少有( ceil(m/2) )个儿子结点,m 阶B+树中每个结点(除根外)最多有( m )个儿子结点. 2、n(n>0)个结点构成的二叉树，叶结点最多有( floor((n+1)/2) )个，最少有( 1 )个。若二叉树有m 个叶结点，则度为2的结点有( m-1 )个。 3、顺序查找方法适用于存储结构为( 顺序表和线性链表 )的线性表，使用折半查找方法的条件是(查找表为顺序存贮的有序表 ) 4、广义表A=(( )，(a ，(b ，c))，d)的表尾Gettail(A)为( ((a,(b,c)),d) ) 5、直接插入排序，起泡排序和快速排序三种方法中，( 快速排序 )所需的平均执行时间最小；( 快速排序 )所需附加空间最大。 二、选择(10分) 1、倒排文件的主要优点是：( C ) A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为( C ) y=0; while(n>=(y+1)*(y+1)) { y++; } A 、O(n) B 、O(n 2) C 、 O(sqrt(n)) D 、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( C ) A 、二叉排序树 B 、哈夫曼树 C 、堆 D 、AVL 树 4、栈和队列都是（ B ） A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5、用顺序查找方法查找长度为n 的线性表时，在等概率情况下的平均查找长度为（ D ） A 、n B 、n/2 C 、(n-1)/2 D 、(n+1)/2 三、简答（30分） 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ 和BCDAFEHJIG ，试给出该二叉树的后序序列并绘出该二叉树对应的森林。 院（系） 班级 姓名 学号 ……………………………………………装…………………………订………………………线……………………………………………数据结构(C语言版)第三版__清华大学出版社_习题参考答案
数据结构(C语言版)期末复习
数据结构c语言版期末考试复习试题
数据结构C语言版第2版课后习题答案
数据结构C语言版第2版课后习题答案
数据结构复习题集答案(c语言版严蔚敏)
数据结构C语言版第一二章习题答案
数据结构(c语言版)第三版清华大学出版社习题参考答案
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构(c语言版)课后习题答案完整版
《数据结构》c语言版
数据结构C语言版期末考试题库单选题
严蔚敏数据结构题集(C语言版)完整
《数据结构(C语言描述)》期末试卷要点
- 数据结构C语言版章节练习题
- 数据结构(C语言版)(第三版) 第六章 树
- 数据结构C语言版第三版清华大学出版社习题参考答案
- 数据结构(C语言版)第三版__清华大学出版社_习题参考答案
- 严蔚敏数据结构题集(C语言版)完整
- 数据结构c语言版课后习题答案完整版
- 数据结构c语言版习题集答案
- 数据结构(C语言版)第三版__清华大学出版社_习题参考答案
- 数据结构C语言版第2版课后习题答案
- 数据结构C语言版(严蔚敏)习题答案
- 数据结构(c语言版)第三版习题解答
- (完整版)数据结构(c语言版)课后习题答案完整版资料
- 数据结构C语言第三版习题5参考答案
- 数据结构c语言版期末考试复习试题
- 数据结构(c语言版)课后习题标准答案完整版
- 数据结构(c语言版)课后习题答案完整版
- 数据结构(c语言版)第三版习题解答
- 数据结构(c语言版)课后习题答案完整版资料
- 数据结构C语言版第2版课后习题答案
- 数据结构c语言第三版,邓文华编习题