数据结构(计算机科学与技术).doc

数据结构（计算机科学与技术本科）第一部分 客观题一、单项选择（每题2分，共20分）1、设n为正整数。则下面程序段的时间复杂度为_。k=0; for(i=1;i=n;i+) for(j=i;jnext;q = head;while (p != NULL & p-data next;p = (ListNode *)malloc(sizeof(ListNode);p-data = x;p-next = q-next;q-next = p;2、假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。1. typedefcharQElemType;2. typedefstruct3. QElemTypeelemMAXQSIZE;4. intlength;5. intrear;6. CLenQueue;7. StatusEnCQueue(CLenQueue&Q,QElemTypex)8. 9. if(Q.length=MAXQSIZE)10. returnERROR;/循环队列满11. 12. if(MAXQSIZE-1!=Q.rear)13. +Q.rear;14. Q.elemQ.rear=x;15. 16. else/rear指向循环队列的末尾时，作特殊处理使其构成循环17. Q.rear=0;18. Q.elemQ.rear=x;19. 20. +Q.length;/当前元素个数+121. returnOK;22. 23. 24. StatusDeCQueue(CLenQueue&Q,QElemType&x)25. 26. if(!Q.length)27. returnERROR;/循环队列空28. 29. if(Q.rear+1=Q.length)/当rear的下标大于对头指向的下标时30. x=Q.elemQ.rear+1-Q.length;31. 32. else/当rear的下标小于队头下标时33. x=Q.elemMAXQSIZE+Q.rear+1-Q.length;34. 35. -Q.length;/当前元素个数-136. returnOK;37. 38. #include39. #include40. #defineQUEUE_SIZE1041. /*循环队列结构体*/42. typedefstruct43. intfront;/*队列头*/44. intrear;/*队列尾*/45. intlength;/*记录队列元素个数*/46. intdataQUEUE_SIZE;/*存放队列元素值的数组*/47. CirQueue;48. /*初始化队列*/49. voidinitQueue(CirQueue*Q)50. 51. Q-front=Q-rear=0;52. Q-length=0;53. 54. /*判断队列是否为空*/55. intQueueEmpty(CirQueue*Q)56. 57. returnQ-length=0;58. 59. /*判断队列满*/60. intQueueFull(CirQueue*Q)61. 62. returnQ-length=QUEUE_SIZE;63. 64. /*入队列*/65. voidEnQueue(CirQueue*Q,intdata)66. 67. if(QueueFull(Q)68. printf(队列已经满了.n);69. Q-length+;/*队列元素个数加1*/70. Q-dataQ-rear=data;/*将新元素插入队尾*/71. Q-rear=(Q-rear+1)%QUEUE_SIZE;/*将队尾加1*/72. 73. /*出队列*/74. intDequeue(CirQueue*Q)75. 76. inttemp;77. if(QueueEmpty(Q)78. printf(队列已经为空!n);79. temp=Q-dataQ-front;80. Q-length-;/*队列元素个数减1*/81. Q-front=(Q-front+1)%QUEUE_SIZE;/*队列头加1*/82. returntemp;83. 84. /*测试程序*/85. intmain()86. 87. CirQueueQ;88. intinput=0;/*入队数据，由用户输入*/89. /*初始化队列*/90. initQueue(&Q);91. printf(请输入入队数据:n);92. /*入队操作*/93. while(!QueueFull(&Q)94. 95. scanf(%dn,&input);96. EnQueue(&Q,input);97. 98. printf(出队数据:n);99