下载文档原格式
习题九一、单选题1、已知：int *p,a；则语句"p=&a；"中的运算符"&"的含义是（）。
A）位与运算 B）逻辑与运算 C）取指针内容D）取变量地址2、已知：int a,x；则正确的赋值语句是（）。
A）a=(a[1]+a[2])/2 B）a*=*a+1; C）a=(x=1,x++,x+2); D）a="goog";3、已知：int a,*p=&a; 则下列函数调用中错误的是（）。
A）scanf("%d",&a); B）scanf("%d",p); C）printf("%d",a); D）printf("%d",p);4、main（argc,argv）中形式参数argv的正确说明形式应当为（）。
A）char *argv[ ] B）char argv[ ][ ] C）char argv[ ] D）char *argv5、说明语句"int (*p)(); "的含义是（）。
A）p是一个指向一维数组的指针变量B）p是一个指针变量，指向一个整型数据C）p是一个指向函数的指针，该函数的返回值是一个整型D）以上都不对6、设有说明int(*ptr)[M]；其中的标识符ptr是（）。
A）M个指向整型变量的指针B）指向M个整型变量的函数指针C）一个指向有M个整型元素的一维数组的指针D）具有M个指针元素的一维指针数组，每个元素都只能指向整型变量7、已知：double *p[6]; 它的含义是（）。
A）p是指向double型变量的指针 B）p是double型数组C）p是指针数组 D）p是数组指针8、已知函数说明语句：void *f(); 则它的含义是（）。
A）函数f的返回值是一个通用型的指针 B）函数f的返回值可以是任意的数据类型C）函数f无返回值D）指针f指向一个函数，该函数无返回值9、已知：char s[10],*p=s，则在下列语句中，错误的语句是（）。
第9课时习题课一、知识回顾函数的的单调性与奇偶性概念及注意点二、小题训练1、判断下列函数的奇偶性（1）()f x = （3）3()3f x x x x x =+-（2）2()(1)1x f x x x =--g （4）2()3f x x x x =+- 2、已知函数2()2(1)2f x x a x =+-+在区间(,4]-∞上是减函数，则实数a 的取值范围为3、 下列结论正确的是______________________(填代号)。
A. 函数(y kx k =为常数，0k <）在Ｒ上是增函数；B 函数在2y x =在Ｒ上是增函数； C.1y x =在定义域内为减函数；D 。
1y x=在(,0)-∞上为减函数 4．函数242y x x =-+-在区间[1,4]上的最小值是________ ；最大值是 ；单调递增区间是 ；单调递减区间是5．设偶函数()f x 的定义域为[5,5]-，若当[0,5]x ∈时()f x 单调递增，且(3)0f =，则不等式()0f x <的解集是 ．6求证：函数3()f x x x =+在(,)-∞+∞上是增函数。
7.21()(1)2f x x a =-+的定义域和值域都是[1,](1)b b >，求,a b 的值。
8.任意,x y R ∈且,0x y ≠，已知函数()(0)y f x x =≠满足()()().f xy f x f y =+求证：（1）(1)(1)0;f f =-= (2)()y f x =为偶函数。
9.已知函数()f x 是偶函数，且在(0,)+∞上是减函数，试判断()f x 在(,0)-∞上是增函数还是减函数，并加以证明.第九课时 函数性质习题课（学案）1.判断下列函数的奇偶性：()3(1)2;f x x x =- ()42(2)232;f x x x =++（3）()()21f x x x =+； （4）()1;f x x=（5()f x = （6）()2121;f x x x =+--2． 函数26,[1,2]()7,[1,1]x x f x x x +∈⎧=⎨+∈-⎩，则()f x 的最大值，最小值分别是______________ 3．已知函数()f x 是区间(0,)+∞上的减函数，那么2(1)f a a -+与3()4f 的大小关系是．4．已知()f x 是奇函数，当0,()(1),x f x x x >=+当0x <时，()f x = ．5．已知函数2()(231)f x ax bx c a x =++--≤≤是偶函数，则______,______.a b ==6．已知函数2()22(0)f x ax ax b a =-++≠在[2,3]上有最大值５和最小值２，求,a b 的值．7．设()f x 和()g x 都为奇函数，()()()2H x af x bg x =++在区间()0,+∞上有最大值5，求()H x 在区间(),0-∞上的最小值。
清华大学课程讲义-数据结构答案第9章9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。
并说明做了多少次关键码比较。
(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序(4) 快速排序(5) 直接选择排序(6) 锦标赛排序(7) 堆排序(8) 二路归并排序(9) 基数排序【解答】9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。
在快速排序过程中有这种现象吗？【解答】如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。
例如，57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动6 7 9 11 13 19 57 40 38 34 48 756 7 9 11 13 19 34 57 40 38 48 756 7 9 11 13 19 349-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。
如此反复进行。
【解答】template <class Type> void dataList<Type> :: shake_Sort ( ) {//奇数趟对表Vector从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列//中最大的关键码移到序列尾部。
严蔚敏《数据结构（c语言版）习题集》算法设计题第九章答案第九章查找int Search_Sq(SSTable ST int key)//在有序表上顺序查找的算法监视哨设在高下标端{ST elem[ST length+ ] key=key;for(i= ;ST elem[i] key>key;i++);if(i>ST length||ST elem[i] keyreturn i;}//Search_Sq分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.9.26int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算法{if(low>high) return 0; //查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key) return mid;else if(ST.elem[mid].key>key)return Search_Bin_Recursive(ST,key,low,mid-1);else return Search_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive9.27int Locate_Bin(SST able ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号{int *r;r=ST.elem;if(keyelse if(key>=r[ST.length].key) return ST.length;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key>=r[mid].key&&keyreturn mid;else if(keyelse low=mid;} //本算法不存在查找失败的情况,不需要return 0;}//Locate_Bin9.28typedef struct {int maxkey;int firstloc;} Index;typedef struct {int *elem;int length;Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找int blknum; //块的数目} IdxSqList; //索引顺序表类型int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素low=1;high=L.blknum;found=0;while(low<=high&&!found) //折半查找记录所在块号mid{mid=(low+high)/2;if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)found=1;else if(key>L.idx[mid].maxkey)low=mid+1;else high=mid-1;}i=L.idx[mid].firstloc; //块的下界j=i+blksize-1; //块的上界temp=L.elem[i-1]; //保存相邻元素L.elem[i-1]=key; //设置监视哨for(k=j;L.elem[k]!=key;k--); //顺序查找L.elem[i-1]=temp; //恢复元素if(kreturn k;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedef struct {LNode *h; //h指向最小元素LNode *t; //t指向上次查找的结点} CSList;LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{if(L.t->data==key) return L.t;else if(L.t->data>key)for(p=L.h,i=1;p->data!=key;p=p->next,i++);elsefor(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);L.t=p; //更新t指针return p;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedef struct {DLNode *pre;int data;DLNode *next;} DLNode;typedef struct {DLNode *sp;int length;} DSList; //供查找的双向循环链表类型DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{p=L.sp;if(p->data>key){while(p->data>key) p=p->pre;L.sp=p;}{while(p->data next;L.sp=p;}return p;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31int last=0,flag=1;int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{if(T->lchild&&flag) Is_BSTree(T->lchild);if(T->datalast=T->data;if(T->rchild&&flag) Is_BSTree(T->rchild);return flag;}//Is_BSTree9.32int last=0;void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x 的最大元素和大于x的最小元素{if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现if(last data>=x) //找到了小于x的最大元素printf("a=%d\n",last);if(last<=x&&T->data>x) //找到了大于x的最小元素printf("b=%d\n",T->data);if(T->rchild) MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素{if(T->rchild) Print_NLT(T->rchild,x);if(T->dataprintf("%d\n",T->data);if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历}//Print_NLT9.34void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间{if(T->rchild) Delete_NLT(T->rchild,x);if(T->dataq=T;T=T->lchild;free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根if(T) Delete_NLT(T,x); //继续在左子树中执行算法}//Delete_NLT9.35void Print_Beeen(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{p=T;while(!p->ltag) p=p->lchild; //找到最小元素while(p&&p->data{if(p->data>a) printf("%d\n",p->data); //输出符合条件的元素if(p->rtag) p=p->rtag;else{p=p->rchild;while(!p->ltag) p=p->lchild;} //转到中序后继}//while}//Print_Beeen9.36void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x{if(T->data{if(T->rtag) //T没有右子树时,作为右孩子插入{p=T->rchild;q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->rchild=q;T->rtag=0;q->rtag=1;q->rchild=p; //修改原线索}else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中}//ifelse if(T->data>x) //插入到左子树中{if(!T->lchild) //T没有左子树时,作为左孩子插入{q=(BiThrNode*)malloc(sizeof(BiThrNode));q->data=x;T->lchild=q;q->rtag=1;q->rchild=T; //修改自身的线索}else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中}//if}//BSTree_Insert_Key9.37。
数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。
3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。
4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。
5.以三元组顺序表存放的稀疏矩阵的转置算法。
6.⼆叉树的性质及其四种遍历算法。
7.森林与⼆叉树的相互转换。
8.WPL、前缀编码的概念，哈夫曼树的构造算法。
9.图的相关概念，邻接矩阵及邻接表的存储结构。
10.图的深度优先/⼴度优先遍历算法。
11.最⼩⽣成树的两种算法。
12.拓扑排序的意义和算法。
13.最短路径算法。
14.顺序表、有序表的查找算法。
15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。
16.哈希表的相关概念，常⽤的冲突处理⽅法。
17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。
注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。
2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。
其他的算法则可能会出现在“算法题”中。
⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。
（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。
（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。
A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。
A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。
A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。
