| 显示联大系统河南理工大学数据结构所有答案 |
|
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C.
|
答案是：①A和D是合法序列，B和C 是非法序列。 ②设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){cout<<“序列非法”<
|
|
从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。
|
答案是：float expr( ) //从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。 ｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。 cin>>x;//x是字符型变量。 while(x!=’$’) {switch {case‘0’<=x<=’9’: while((x>=’0’&&x<=’9’)||x==’.’) //拼数 if(x!=’.’) //处理整数 {num=num*10+（ord(x)-ord(‘0’)）; cin>>x;} else //处理小数部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; cin>>x; } }//else push(OPND,num); num=0.0;//数压入栈，下个数初始化 case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break; case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break; case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch cin>>x;//读入表达式中下一个字符。 }//结束while（x！=‘$’） cout<<“后缀表达式的值为”<
|
|
设从键盘输入一整数的序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。
|
答案是：#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {cin>>x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。 ｛if(top==maxsize-1){cout<<“栈满”<
|
|
回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
|
答案是：#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量长度 for ( i=0; i
|
|
将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进
|
答案是：(1) 栈初始化 int Init() {S.top[0]=-1; S.top[1]=m; return 1; //初始化成功 } (2) 入栈操作： int push(stk S ,int i,int x) ∥i为栈号，i=0表示左栈，i=1为右栈，x是入栈元素。入栈成功返回1，失败返回0 {if(i<0||i>1){ cout<<“栈号输入不对”<1){cout<<“栈号输入错误”<
|
|
系统软件通常由____、____、____和____等组成。
|
答案是：操作系统、语言处理程序、数据库管理程序、服务程序
|
|
算机安全是指计算机财产的安全。计算机财产包括____和____。
|
答案是：
系统资源、信息资源
|
|
非空的线性结构中，有且仅有一个元素没有直接前驱。
|
答案是：
对
|
|
下面是删除带头结点的单链表中首元结点的程序片段，Ｌ为头指针，则应在空的位置填上 。p=L->next;if(p) { L->next= ; free(p);}
|
答案是：
p->next
|
|
已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。
|
答案是：void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i
|
|
已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。
|
答案是：void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换 p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱 }∥算法exchange结束。
|
|
设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。
|
答案是：void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->datanext; // 查找第一个值 ≥maxk的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 }//if }
|
|
设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
|
答案是：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; } }
|
|
设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
|
答案是：
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的值大于pmax的值，则重新赋值 p=p->next;//遍历链表 } return pmax->data;
|
|
设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。
|
答案是：
void DisCompose(LinkedList A) { B=A; B->next= NULL; ∥B表初始化 C=new LNode;∥为C申请结点空间 C->next=NULL; ∥C初始化为空表 p=A->next; ∥p为工作指针 while(p!= NULL) { r=p->next; ∥暂存p的后继 if(p->data<0) {p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法 else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法 p=r;∥p指向新的待处理结点。 } }
|
|
已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
|
答案是：
void Difference（LinkList& La, LinkList& Lb,int *n） {∥差集的结果存储于单链表La中，*n是结果集合中元素个数，调用时为0 pa=La->next; pb=Lb->next; ∥pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 pre=La; ∥pre为La中pa所指结点的前驱结点的指针 while（pa&&pb） {if（pa->datadata）{pre=pa;pa=pa->next;*n++;} ∥ A链表中当前结点指针后移 else if（pa->data>q->data）q=q->next; ∥B链表中当前结点指针后移 else {pre->next=pa->next; ∥处理A，B中元素值相同的结点，应删除 u=pa; pa=pa->next; delete u;} ∥删除结点 } }
|
|
已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。
|
答案是：
void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) { pa=La->next;pb=Lb->next; pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) { if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->datadata) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;} } while(pa) {u=pa; pa=pa->next; delete u;}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间 pc->next=null;∥置链表尾标记。 delete Lb; //释放Lb的头结点 }
|
|
将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。
|
答案是：oid MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next=NULL; while(pa||pb ) {//只要存在一个非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表为空，用q指向pb，pb指针后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表为空，用q指向pa，pa指针后移 else if(pa->data<=pb->data) {q=pa; pa=pa->next;} //取较小者（包括相等）La中的元素，用q指向pa，pa指针后移 else {q=pb; pb=pb->next;} //取较小者Lb中的元素，用q指向pb，pb指针后移 q->next = Lc->next; Lc->next = q; //将q指向的结点插在Lc 表的表头结点之后 } delete Lb; //释放Lb的头结点 }
|
|
将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
|
答案是：
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) {if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;} //取较小者La中的元素，将pa链接在pc的后面，pa指针后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移 else //相等时取La中的元素，删除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点 }
|
|
下面程序段的时间复杂度是（ ）。x=0;for(i=1;i<=n;i=2*i) for(j=1;j<=n;j++) x++;
|
答案是：
O(nlog2n)
|
|
数据结构是相互之间存在一种或多种特定关系的（ ）的集合。
|
答案是：
数据元素
|
|
“计算机辅助制造”的英文缩写是____。
|
答案是：
CAM
|
|
抽象数据类型
|
答案是：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
|
|
存储结构
|
答案是：
数据对象在计算机中的存储表示，也称为物理结构。
|
|
数据对象
|
答案是：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
|
|
数据项
|
答案是：
是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
|
|
数据元素
|
答案是：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
|
|
线性表的顺序存储结构比链式存储结构更好。
A.正确
B.错误
|
答案是：参考答案：错
|
|
为什么计算机内一定要配置端口或接口？
|
答案是：
I/O设备一般不和微机内部直接相连，而是必须通过I/O接口与微机内部进行信息交换。 首先，微机和I/O设备两者的信息类型和格式可能不一样。外设种类繁多，信号类型十分复杂，它既可以是机械式的、电动式的或电子式的，也可以是其他形式的；所使用的信号可以是数字量或模拟量，也可以是开关量；即使是数字量，也可能与微机在信号线的功能定义、逻辑定义上都不一致；必须通过I/O接口实现微机与外部设备的隔离和信号转换。 其次，微机和I/O设备信号传输处理的速度往往不匹配，信号时序有很大差别，必须通过I/O接口来进行缓冲和协调。 再次，随着计算机技术的发展，I/O设备的种类日益丰富，一台多媒体微机可能要配置数十个I/O设备，若不通过接口，而由CPU直接对I/O设备的操作实施控制，就会使CPU一直忙于与外设打交道，大大降低CPU的效率。 最后，若I/O设备直接由CPU控制，也会使外设的硬件结构依赖于CPU，对外设本身的发展不利。I/O接口的引入，使得CPU对I/O设备的操作转化为对I/O接口的操作。 可见，I/O接口是微机与外部设备之间进行信息交换的中转站，是任何微机应用系统必不可少的重要组成部分。
|
|
存储结构由哪两种基本的存储方法实现？
|
答案是：1）顺序存储结构，顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。（2）链式存储结构，顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
|
|
试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
|
答案是：
例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。
|
|
试分析下面各程序段的时间复杂度。x=0; for(i=1; i
|
答案是：O(n2)
|
|
试分析下面各程序段的时间复杂度。i=1; while(i<=n) i=i*3;
|
答案是：
O(log3n)
|
|
试分析下面各程序段的时间复杂度。s=0; for i=0; i
|
答案是：
O(n2)
|
|
试分析下面各程序段的时间复杂度。for (i=0; i
|
答案是：
O(m*n)
|
|
试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++;
|
答案是：
O(1)
|
|
下列排序方法中，（ ）是稳定的排序方法。
A..希尔排序
B..冒泡排序
C..快速排序
D.归并排序
|
答案是：参考答案：BD
|
|
快速排序在最坏情况下的时间复杂度为（ ）。
A.O(log2n)
B.O(nlog2n)
C.0(n)
D.0(n2)
|
答案是：参考答案：D
|
|
从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
|
答案是：参考答案：D
|
|
对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
|
答案是：参考答案：B
|
|
对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。
A.n+1
B.n
C.n-1
D.n(n-1)/2
|
答案是：参考答案：D
|
|
快速排序在下列（ ）情况下最易发挥其长处。
A.被排序的数据中含有多个相同排序码
B.被排序的数据已基本有序
C.被排序的数据完全无序
D.被排序的数据中的最大值和最小值相差悬殊
|
答案是：参考答案：C
|
|
对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A.O(n)
B.O(n2)
C.O(nlog2n)
D.O(n3)
|
答案是：参考答案：B
|
|
若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，
|
答案是：参考答案：C
|
|
下列关键字序列中，（ ）是堆。
A.16，72，31，23，94，53
B.94，23，31，72，16，53
C.16，53，23，94，31，72
D.16，23，53，31，94，72
|
答案是：参考答案：D
|
|
堆是一种（ ）排序。
A.插入
B.选择
C.交换
D.归并
|
答案是：参考答案：B
|
|
堆的形状是一棵（ ）。
A.二叉排序树
B.满二叉树
C.完全二叉树
D.平衡二叉树
|
答案是：参考答案：C
|
|
若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。
A.79，46，56，38，40，84
B.84，79，56，38，40，46
C.84，79，56，46，40，38
D.84，
|
答案是：参考答案：B
|
|
下述几种排序方法中，要求内存最大的是（ ）。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
|
答案是：参考答案：C
|
|
下述几种排序方法中，（ ）是稳定的排序方法。
A.希尔排序
B.快速排序
C.归并排序
D.堆排序
|
答案是：参考答案：C
|
|
数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。
A.冒泡排序
B.快速排序
C.简单选择排序
D.堆排序
|
答案是：参考答案：D
|
|
下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序
B.快速排序
C.冒泡排序
D.堆排序
|
答案是：参考答案：A
|
|
从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
|
答案是：参考答案：C
|
|
下面关于B-和B+树的叙述中，不正确的是（ ）。
A.．B-树和B+树都是不平衡的多叉树
B.B-树和B+树都可用于文件的索引结构
C.B-树和B+树都能有效地支持顺序检索
D.B-树和B+树都能有效地支持随机检索
|
答案是：参考答案：AC
|
|
采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。
A.不一定都是同义词
B.一定都是同义词
C.一定都不是同义词
D.都相同
|
答案是：参考答案：A
|
|
对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
A.(n-1)/2
B.n/2
C.(n+1)/2
D.n
|
答案是：参考答案：C
|
|
适用于折半查找的表的存储方式及元素排列要求为（ ）。
A.链接方式存储，元素无序
B.链接方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
|
答案是：参考答案：D
|
|
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。
A.顺序查找
B.折半查找
C.分块查找
D.哈希查找
|
答案是：参考答案：C
|
|
折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A.20，70，30，50
B.30，88，70，50
C.20，50
D.30，88
|
答案是：参考答案：A
|
|
对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。
A.3
B.4
C.5
D.6
|
答案是：参考答案：B
|
|
目前为：
2/4
页
首页 上页 下页 尾页
|
